CD*: A Real-Time Resolution Optimal Re-Planner for Globally Constrained Problems

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Robotics

Many problems in robotics and AI, such as the find-path problem, call for optimal solutions that satisfy global constraints. The problem is complicated when the cost information is unknown, uncertain, or changing during execution of the solution. Such problems call for efficient re-planning during execution to account for the new information acquired. This paper presents a novel real-time algorithm, Constrained D* (CD*), that re-plans resolution optimal solutions subject to a global constraint. CD* performs a binary search on a weight parameter that sets the balance between the optimality and feasibility cost metrics. In each stage of the search, CD* uses Dynamic A* (D*) to update the weight selection for that stage. On average, CD* updates a feasible and resolution optimal plan in less than a second, enabling it to be used in a real-time robot controller. Results are presented for simulated problems. To the author’s knowledge, CD* is the fastest algorithm to solve this class of problems.