Multi-Robot Navigation and Exploration in Graphs with Entrance-Dependent Identification of the Edges

• Pablo Sampaio UFRPE
• Jonatan Pereira UFRPE

Abstract

We propose two multi-robot algorithms to enable navigation in graph environments where numerical ports identify edges incidents to each node. This identification, however, varies dynamically according to the entrance edge used by the robot to reach the node. A new exploration algorithm called ECEP writes information on the nodes that can later be used by the new navigation algorithm NCEP to properly navigate to any given neighbor. Both algorithms require minimal memory space from the agent and from each node. Simulations showed that it requires an average exploration time O(G/k), for k robots. Both were also successfully implemented on robots with simple hardware.

Keywords: Navigation, Robot sensing systems, Robot kinematics, Memory management, Image edge detection, Heuristic algorithms