Real-Time Edge Follow: A New Paradigm to Real-Time Path Search.

摘要

Path searching and mission planning are challenging problems in many domains such as war games, robotics, military mission planning, computer-generated forces, etc. The objective of this study is to develop a real-time pathplanning algorithm to accomplish specified missions on large landscapes. For that purpose, a real-time goaldirected path search algorithm, Real-Time Edge Follow (RTEF), which can work on fully known, partial known or completely unknown maze environments, is developed. RTEF aims to find a path from a staring point to a static or dynamic target point in real-time. The basic idea behind the RTEF is to let the agent eliminate closed directions (the directions that cannot reach the target point) by analyzing obstacle edges in order to decide on which way to go (open directions). For instance, if the agent has a chance to realize that moving to north and east won't let him reach the goal state (although the target is at north-east), then he will prefer going to south or west. RTEF finds out these open and closed directions, so decreasing the number of choices the agent has and significantly shortening the path. The method is tested on large mazes and compared with Real-Time A*. We observed that RTEF always performs much better than RTA* when solution quality is considered and usually better when total time spent to reach the goal state is considered (especially on complicated mazes). RTEF frequently gives high solution quality, which is in most cases near to optimal solution, and never needs to return to a previously visited cell while on the way.