An Optimal Approach to Anytime Task and Path Planning for Autonomous Mobile Robots in Dynamic Environments

The study of combined task and path planning has mainly focused on feasibility planning for high-dimensional, complex manipulation problems. Yet the integration of symbolic reasoning capabilities with geometric knowledge can address optimal planning in lower dimensional problems. This paper presents a dynamic, anytime task and path planning approach that enables mobile robots to autonomously adapt to changes in the environment. The planner consists of a path planning layer that adopts a multi-tree extension of the optimal Transition-based Rapidly-Exploring Random Tree algorithm to simultaneously find optimal paths for all movement actions. The corresponding path costs, derived from a cost space function, are incorporated into the symbolic representation of the problem to guide the task planning layer. Anytime planning provides continuous path quality improvements, which subsequently updates the high-level plan. Geometric knowledge of the environment is preserved to efficiently re-plan both at the task and path planning level. The planner is evaluated against existing methods for static planning problems, showing that it is able to find higher quality plans without compromising planning time. Simulated deployment of the planner in a partially-known environment demonstrates the effectiveness of the dynamic, anytime components.