Navigation for Mobile Autonomous Robots and Their Formations: an Application of Spatial Reasoning Induced from Rough Mereological Geometry

Abstract

This Chapter is intended as a sequel to our Chapter 21 in the book on "Mobile Robots Motion Planning. New Challenges" by this Publisher. It is now commonly accepted that problems of planning and navigation are inseparable: "Most recent contribution to the field combine effective algorithms tested on significant problems, along with some formal guarantees of performance" (J.-C. Latombe in Foreword to "Principles of Robot Motion. Theory, Algorithms and Implementations" by H. Choset et al.). Therefore, as with the former Chapter, we provide in this Chapter planning mechanisms along with navigation tests and a theoretical analysis of underlying constructs. We extend our scope of analysis by considering formations of mobile autonomous robots. We introduce a definition of a robot formation, based on the spatial relation of betweenness and we give a treatment of planning and navigation problems for robot formations. In our investigations into problems of multirobot planning and navigation, we apply rough mereological theory of spatial reasoning. This theory is briefly recalled in this Chapter for completeness sake. The software system Player/Stage is employed as means of simulation and visualization of robot trajectories to chosen goals. To this end, it has been provided with SQL functions rendering predicates of rough mereological geometry. Robotics of autonomous mobile robots presents the most intricate field for applications of techniques of artificial intelligence, decision making and cognitive methods. Among the basic problems in this area are planning and navigation problems and we are concerned with them both in their mutual bond.The planning and navigation problem for mobile robots is addressed from many angles and a multitude of approaches and techniques have emerged; it suffices to mention a division of planners according to assumptions about robot equipment and abilities as well theoretical principles used in planner construction, from simple bug-type algorithms though potential functions and potential field based strategies to roadmaps constructed by exploiting visibility in configuration spaces, metric-based ideas like Voronoi diagrams and graphs, cell decompositions of various types, and probabilistic (sampling) planners allowing for incremental space exploration by building trees of configuration points like EST-trees or 16 www.intechopen.com