Improving efficiency in mobile robot task planning through world abstraction

Task planning in mobile robotics should be performed efficiently, due to real-time requirements of robot-environment interaction. Its computational efficiency depends both on the number of operators (actions the robot can perform without planning) and the size of the world states (descriptions of the world before and after the application of operators). Thus, in real robotic applications, where both components can be large, planning may turn inefficient, and even unsolvable. In the artificial intelligence (AI) literature on planning, little attention has been put into efficient management of large-scale world descriptions. In real large-scale situations, conventional AI planners (in spite of the most modern improvements) may consume intractable amounts of storage and computing time, due to the huge amount of information. This paper proposes a new approach to task planning called hierarchical task planning through world abstraction that, by hierarchically arranging the world representation, becomes a good complement of Stanford Research Institute Problem Solver-style planners, significantly improving their computational efficiency. Broadly speaking, our approach works by first solving the task-planning problem in a highly abstracted model of the environment of the robot, and then refines the solution under more detailed models, where irrelevant world elements can be ignored, due to the results previously obtained at abstracted levels. Among the different implementations that can be made with our general strategy, we describe two that use a graph-based hierarchical world representation named the annotated and hierarchical graph. We show experiments, as well as results of a mobile robot operating in a large-scale environment, that demonstrate an important improvement in the efficiency of our algorithms with respect to conventional (both hierarchical and nonhierarchical) planning and their nice integration with existing planners.