Relational methods for topological path planning

Relational methods are used on topological path planning 20220209184809 mapping the world as a graph of nodes and edges. Nodes represent gateways, goals or landmarks and edges navigable paths.

An example of relational method can be found on (Kuipers and Byun 1991). They state, first and foremost, for making map construction possible, we need to properly detect distinctive places on the environment (landmark that can be detected from a region called neighborhood). We can build a multi-level hierarchy where:

• Lowest level represents landmarks and procedural knowledge to travel them
• Middle level, where there is a topological and connectivity representation of previous landmarks
• Higher level, where there are metric distances, orientations and servers to locate on a coordinate system

With this, when the robot detects a distinctive place, it can position itself on a certain place relative to the landmark, and use this information to locate itself on the map that it’s known. From one node o another, the arc represents how to move from a landmark to another, using a local-control strategy for the pair.

Advantages / Disadvantages

• ADV: distinctive places eliminate navigation errors on each node.
• ADV: landmark discovery is supported.
• DISADV: good distinctive places are hard to come by.
• DISADV: optimal local-control strategies are difficult to learn.
• DISADV: indistinguishable locations are a challenge.

Notes References

20220209184809 Topological path planning

20210514183815 INDEX - Robotics

References

(Murphy 2000)

Kuipers, Benjamin, and Yung-Tai Byun. 1991. “A Robot Exploration and Mapping Strategy Based on a Semantic Hierarchy of Spatial Representations.” Robotics Auton. Syst. 8: 47–63.

Murphy, Robin. 2000. Introduction to AI Robotics. Intelligent Robotics and Autonomous Agents. Cambridge, Mass: MIT Press.