Simultaneous Path Planning and Topological Mapping (SP2ATM) for environment exploration and goal oriented navigation

In this paper, a novel approach, Simultaneous Path Planning and Topological Mapping (SP(2)ATM), is presented to address the problem of path planning in unknown environments by concurrent and incremental construction of a map, which strictly exploits only the topology rather than grid representation. For local topological information representation, a new concept, Admissible Space Tree (AST), is presented to describe the admissible free space in the environment as a group of nodes and graphs. The global map of the explored environment is encoded in a Hierarchical Topological Map (HTM), which by embedding the AST, serves as the least information to facilitate path planning. For simplicity, the algorithm is implemented in a planar space on our differentially driven mobile robot X1, based on its range sensing and self-localization capabilities. Experiments' results show that SP(2)ATM is effective and globally convergent in complex and dynamic environments. (C) 2010 Elsevier B.V. All rights reserved.