Multi-robot exploration of unknown environments with identification of exploration completion and post-exploration rendez-vous using ant algorithms

Mihai Andries 1, * François Charpillet 1
* Corresponding author
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : This paper presents a new ant algorithm for the navigation of several robots, whose objective is to autonomously explore an unknown environment. When the coverage is com- pleted, all robots move to a previously defined meeting point. The approach that we propose in this paper for solving this problem, considers that the robots build, while moving, a common and shared representation of the environment. In this representation, the environment is viewed as a graph (typically a set of connected cells in a regular grid), each grid cell having a local memory able to store a limited amount of data. A robot can write numbers on the cell on which it is lying. It can also read the values of the cells in its neighborhood, and perform some simple operations, such as computing the minimum of a set of values. Each robot is capable, contrary to most ant- based approaches, to determine, in a distributed way, when the environment coverage has completed. Few ant algorithms can do that. Brick&Mortar is one of them and this is why it retains a central place in our proposition. The novelty of our approach is that, due to an emerging property of the underlying algorithm, agents will finish their exploration at a pre-defined evacuation point. In addition, several improvements of the original Brick&Mortar algorithm are proposed in this paper, such as the possibility to use better local strategies at the robot level (using, for example, LRTA*). The paper also presents a set of benchmarks against the best existing ant algorithms on several widespread graph topologies.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00913349
Contributor : Mihai Andries <>
Submitted on : Tuesday, December 3, 2013 - 3:21:51 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on : Monday, March 3, 2014 - 11:15:25 PM

Files

Identifiers

  • HAL Id : hal-00913349, version 1

Collections

Citation

Mihai Andries, François Charpillet. Multi-robot exploration of unknown environments with identification of exploration completion and post-exploration rendez-vous using ant algorithms. IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE/RSJ, Nov 2013, Tokyo, Japan. ⟨hal-00913349⟩

Share

Metrics

Record views

531

Files downloads

677