Goal assignment using distance cost in multi-robot exploration
- 1 October 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21530858,p. 3741-3746
Abstract
In this paper, we discuss the problem of goal assignment in the multi-robot exploration task. The presented work is focused on the underlying optimal assignment problem of the multi-robot task allocation that is addressed by three state-of-the art approaches. In addition, we propose a novel exploration strategy considering allocation of all current goals (not only immediate goal) for each robot, which leads to the multiple traveling salesman problem formulation. Although the problem is strongly NP-hard, we show its approximate solution is computationally feasible and its overall requirements are competitive to the previous approaches. The proposed approach and three well-known approaches are compared in series of problems considering various numbers of robots and sensor ranges. Based on the evaluation of the results the proposed exploration strategy provides shorter exploration times than the former approaches.Keywords
This publication has 14 references indexed in Scilit:
- Exploration strategies based on multi-criteria decision making for searching environments in rescue operationsAutonomous Robots, 2011
- On distance utility in the exploration task2011
- Smooth Nearness-Diagram Navigation2008
- Coordinated multi-robot exploration using a segmentation of the environment2008
- Experimental evaluation of some exploration strategies for mobile robots2008
- A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot SystemsThe International Journal of Robotics Research, 2004
- On bending invariant signatures for surfacesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Chained Lin-Kernighan for Large Traveling Salesman ProblemsINFORMS Journal on Computing, 2003
- Decentralized coordination for multirobot explorationRobotics and Autonomous Systems, 1999
- Frontier-based exploration using multiple robots1998