A Hybrid A*/Automaton Approach to On-Line Path Planning with Obstacle Avoidance

Abstract

Autonomous path planning capability is a critical requirement for future unmanned vehicle operations. This paper presents a novel path planning approach for rapid construction of feasible, yet agile, trajectories. The approach relies upon separating the planning task into an on-line and an o-line component. The o-line component consists of building a library of motion primitives using nonlinear simulation, the primitives are then sequenced on-line using an A* search. The main benefit of this separation is that it shifts the computationally intensive work to the o-line component and leaves the on-line task relatively light. A major benefit of using A* is that the search algorithm is unaected by the changes to the library of trim primitives. Thus in the event that a UAVs capabilities are degraded, e.g. due to damage, any unavailable motion primitives are simply removed from the library and A* will not included them in the path construction. To speed up the on-line search time, a sub-optimal modification is made to the standard A* algorithm that delivers a feasible sub-optimal path quickly with relatively small increase in total path cost. Examples of waypoint planning and obstacle avoidance are given to illustrate the path planning approach.