A flooding algorithm for multirobot exploration

Area of Science:

• Robotics
• Artificial Intelligence
• Distributed Systems

Background:

• Efficient multirobot exploration is crucial for tasks like mapping and search and rescue.
• Existing algorithms often face challenges in coordination and minimizing traversal distances.
• Decentralized approaches are desirable for scalability and robustness.

Purpose of the Study:

• To present a novel decentralized multirobot exploration algorithm.
• To reduce exploration time and minimize overall robot traverse distance.
• To analyze and evaluate the algorithm's performance on tree environments.

Main Methods:

• Modeling the environment as a tree structure.
• Implementing a coordination model restricting robots on edges and vertices.
• Utilizing decentralized active landmarks dropped by robots at explored vertices.
• Mathematical analysis of algorithm properties and exploration time bounds on trees.

Main Results:

• The proposed algorithm effectively coordinates robot movement for efficient exploration.
• Mathematical analysis provides bounds on exploration time for tree environments.
• Defined three performance metrics for multirobot algorithms.
• Simulations demonstrate competitive or superior performance compared to multirobot depth-first search (MR-DFS) and single-robot DFS.

Conclusions:

• The decentralized landmark-based coordination algorithm offers an effective solution for multirobot exploration.
• The algorithm demonstrates significant improvements in exploration efficiency.
• The findings provide valuable insights for the design of future multirobot systems.