Full Text:   <426>

Summary:  <132>

CLC number: TP182

On-line Access: 2019-01-30

Received: 2018-09-11

Revision Accepted: 2018-11-27

Crosschecked: 2019-01-08

Cited: 0

Clicked: 804

Citations:  Bibtex RefMan EndNote GB/T7714


Bin Xin


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2019 Vol.20 No.1 P.18-31


A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots

Author(s):  Guan-qiang Gao, Bin Xin

Affiliation(s):  School of Automation, Beijing Institute of Technology, Beijing 100081, China; more

Corresponding email(s):   3120170426@bit.edu.cn, brucebin@bit.edu.cn

Key Words:  Coverage motion planning, Multi-robot system, Auction algorithm, Spanning tree coverage algorithm

Guan-qiang Gao, Bin Xin. A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(1): 18-31.

@article{title="A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots",
author="Guan-qiang Gao, Bin Xin",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots
%A Guan-qiang Gao
%A Bin Xin
%J Frontiers of Information Technology & Electronic Engineering
%V 20
%N 1
%P 18-31
%@ 2095-9184
%D 2019
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1800551

T1 - A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots
A1 - Guan-qiang Gao
A1 - Bin Xin
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 20
IS - 1
SP - 18
EP - 31
%@ 2095-9184
Y1 - 2019
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1800551

The multi-robot coverage motion planning (MCMP) problem in which every reachable area must be covered is common in multi-robot systems. To deal with the MCMP problem, we propose an efficient, complete, and off-line algorithm, named the “auction-based spanning tree coverage (A-STC)'' algorithm. First, the configuration space is divided into mega cells whose size is twice the minimum coverage range of a robot. Based on connection relationships among mega cells, a graph structure can be obtained. A robot that circumnavigates a spanning tree of the graph can generate a coverage trajectory. Then, the proposed algorithm adopts an auction mechanism to construct one spanning tree for each robot. In this mechanism, an auctioneer robot chooses a suitable vertex of the graph as an auction item from neighboring vertexes of its spanning tree by heuristic rules. A bidder robot submits a proper bid to the auctioneer according to the auction vertexes' relationships with the spanning tree of the robot and the estimated length of its trajectory. The estimated length is calculated based on vertexes and edges in the spanning tree. The bidder with the highest bid is selected as a winner to reduce the makespan of the coverage task. After auction processes, acceptable coverage trajectories can be planned rapidly. Computational experiments validate the effectiveness of the proposed MCMP algorithm and the method for estimating trajectory lengths. The proposed algorithm is also compared with the state-of-the-art algorithms. The comparative results show that the A-STC algorithm has apparent advantages in terms of the running time and the makespan for large crowded configuration spaces.




Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]An V, Qu ZH, Roberts R, 2017. A rainbow coverage path planning for a patrolling mobile robot with circular sensing range. IEEE Trans Syst Man Cybern Syst, 48(8):1238-1254.

[2]Azpúrua H, Freitas GM, Macharet DG, et al., 2018. Multirobot coverage path planning using hexagonal segmentation for geophysical surveys. Robotica, 36(8):1144-1166.

[3]Chakraborty A, Misra S, Sharma R, et al., 2017. Observability conditions for switching sensing topology for cooperative localization. Unmann Syst, 5(3):141-157.

[4]Choset H, 2001. Coverage for robotics—a survey of recent results. Ann Math Artif Intell, 31(1-4):113-126.

[5]Dias MB, Zlot R, Kalra N, et al., 2006. Market-based multirobot coordination: a survey and analysis. Proc IEEE, 94(7):1257-1270.

[6]Di Franco C, Buttazzo G, 2016. Coverage path planning for UAVs photogrammetry with energy and resolution constraints. J Intell Robot Syst, 83(3-4):445-462.

[7]Elango M, Nachiappan S, Tiwari MK, 2011. Balancing task allocation in multi-robot systems using K-means clustering and auction based mechanisms. Expert Syst Appl, 38(6):6486-6491.

[8]Fang H, Lu SL, Chen J, et al., 2017. Coalition formation based on a task-oriented collaborative ability vector. Front Inform Technol Electron Eng, 18(1):139-148.

[9]Gabriely Y, Rimon E, 2002. Spiral-STC: an on-line coverage algorithm of grid environments by a mobile robot. Proc IEEE Int Conf on Robotics and Automation, p.954-960.

[10]Gabriely Y, Rimon E, 2003. Competitive on-line coverage of grid environments by a mobile robot. Comput Geom, 24(3):197-224.

[11]Galceran E, Carreras M, 2013. A survey on coverage path planning for robotics. Robot Auton Syst, 61(12):1258-1276.

[12]Gautam A, Murthy JK, Kumar G, et al., 2015. Cluster, allocate, cover: an efficient approach for multi-robot coverage. Proc IEEE Int Conf on Systems, Man, and Cybernetics, p.197-203.

[13]Hazon N, Kaminka GA, 2008. On redundancy, efficiency, and robustness in coverage for multiple robots. Robot Auton Syst, 56(12):1102-1114.

[14]Kapanoglu M, Alikalfa M, Ozkan M, et al., 2012. A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time. J Intell Manuf, 23(4):1035-1045.

[15]Kapoutsis AC, Chatzichristofis SA, Kosmatopoulos EB, 2017. DARP: divide areas algorithm for optimal multi-robot coverage path planning. J Intell Robot Syst, 86(3-4):663-680.

[16]Karapetyan N, Benson K, McKinney C, et al., 2017. Efficient multi-robot coverage of a known environment. Proc IEEE/RSJ Int Conf on Intelligent Robots and Systems, p.1846-1852.

[17]Khamis A, Hussein A, Elmogy A, 2015. Multi-robot task allocation: a review of the state-of-the-art. In: Koubâa A, Martínez-de Dios J (Eds.), Cooperative Robots and Sensor Networks 2015. Springer, Cham.

[18]Khan A, Noreen I, Habib Z, 2017. On complete coverage path planning algorithms for non-holonomic mobile robots: survey and challenges. J Inform Sci Eng, 33(1):101-121.

[19]Kong Y, Zhang MJ, Ye DY, 2016. A group task allocation strategy in open and dynamic grid environments. In: Fukuta N, Ito T, Zhang M, et al., (Eds.), Recent Advances in Agent-Based Complex Automated Negotiation. Springer, Cham.

[20]Li GS, Chou WS, Yin F, 2018. Multi-robot coordinated exploration of indoor environments using semantic information. Sci China Inform Sci, 61(7):79201.

[21]Radmanesh M, Kumar M, Guentert PH, et al., 2018. Overview of path-planning and obstacle avoidance algorithms for UAVs: a comparative study. Unmann Syst, 6(2):95-118.

[22]Rekleitis I, New AP, Rankin ES, et al., 2008. Efficient boustrophedon multi-robot coverage: an algorithmic approach. Ann Math Artif Intell, 52(2-4):109-142.

[23]Tang J, Zhu KJ, Guo HX, et al., 2018. Using auction-based task allocation scheme for simulation optimization of search and rescue in disaster relief. Simul Model Pract Theor, 82:132-146.

[24]Xin B, Gao GQ, Ding YL, et al., 2017. Distributed multi-robot motion planning for cooperative multi-area coverage. Proc 13th IEEE Int Conf on Control & Automation, p.361-366.

[25]Yehoshua R, Agmon N, Kaminka GA, 2016. Robotic adversarial coverage of known environments. Int J Robot Res, 35(12):1419-1444.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE