Directed Graphs and Motion Description Languages for Robot Navigation

We propose a landmark-based representation of maps to be used for robot navigation and exploration. Our approach is aimed towards mobile robots that operate over expansive, imprecisely known terrain without a single "global" map. Instead, a map is pieced together from local terrain and navigation data stored in a directed graph. Each of the graph's vertices contains information describing a landmark locally (e. g. a detailed map of that landmark's immediate surroundings). The geometric relationships between landmarks are unknown. Graph edges store language-based directions that enable a robot to steer between landmarks. These directions are written in the motion description language MDLe, reducing the complexity of the map and making navigation programs robot-independent. Furthermore, the proposed architecture is economical with respect to the amount of storage required to describe far-flung areas of interest. We present preliminary results demonstrating our ideas using an indoor robot.

Authors

• Dimitrios Hristu-Varsakelis
• Sean B. Andersson

Keywords

• Navigation
• Robot kinematics
• Robot sensing systems
• Robotics and automation
• Mobile robots
• Intelligent structures
• Intelligent sensors
• Educational institutions
• Environmental economics
• Remotely operated vehicles
• Directed Graph
• Robot Navigation
• Mobile Robot
• Geometric Relationship
• Coordinate System
• Optimal Control
• Sensor Data
• Landforms
• Path Planning
• Local Map
• Presence Of Uncertainty
• Set Of Sensors
• Global Coordinate System
• Order Of Appearance
• Indoor Navigation