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

Guan-qiang GAO; Bin XIN

doi:10.1631/FITEE.1800551

Your Location：

Home >

Browse articles >

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

Special Issue on Complex System and Intelligent Control | Updated：2022-05-19

- A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots
- A-STC：一种基于拍卖的多机器人协同螺旋生成树覆盖运动规划方法
- Frontiers of Information Technology & Electronic Engineering Vol. 20, Issue 1, Pages: 18-31(2019)
- Affiliations：
  
  School of Automation, Beijing Institute of Technology, Beijing 100081, China
  Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing 100081, China
  Beijing Advanced Innovation Center for Intelligent Robots and Systems, Beijing 100081, China
- Author bio：
  
  [ "Guan-qiang GAO, E-mail: 3120170426@bit.edu.cn" ]
  Bin XIN, E-mail: brucebin@bit.edu.cn
- Funds：
- DOI：10.1631/FITEE.1800551
  CLC： TP182
- Received：11 September 2018，
  
  Revised：2019-;1-;8，
  
  Published：2019-01
- Accepted：
Scan QR Code
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.
DOI：

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. DOI： 10.1631/FITEE.1800551.

摘要

多机器人覆盖运动规划问题是多机器人领域常见问题，要求任务区域内每个点都被机器人传感器或者执行器覆盖一次。提出一种新的有效离线运动规划方法，即基于拍卖的螺旋生成树覆盖（A-STC）算法，解决多机器人覆盖运动规划问题。首先，将布局空间分解为机器人最小覆盖半径两倍的大栅格。基于大栅格之间的连通关系，生成一个无向连接图。机器人可利用巡航无向图中的生成树得到覆盖的运动轨迹。其次，A-STC算法采用拍卖机制构造每个机器人的生成树。在该拍卖机制下，每个机器人都可成为拍卖机器人和竞价机器人。拍卖机器人通过启发式规则从自身生成树的邻居节点中选择一个节点作为拍卖物品。竞价机器人根据拍卖节点的连通关系和运动轨迹的估计长度确定竞标价格。运动轨迹的估计长度主要取决于生成树中的节点和边的类型。最高出价的竞价机器人被选为中标机器人。拍卖过程后，可接受的覆盖运动轨迹可被快速规划生成。计算实验证明了A-STC算法和运动轨迹估计方法的有效性。将提出的算法与前沿算法进行比较，结果显示，所提运动规划方法运行时间和计算结果在大规模算例上具有明显优势。

Abstract

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.

关键词

Keywords

references

V An , , , ZH Qu , , , R Roberts . . A rainbow coverage path planning for a patrolling mobile robot with circular sensing range . . IEEE Trans Syst Man Cybern Syst , , 2017 . . 48 ( ( 8 ): ): 1238 - - 1254 . . DOI: 10.1109/TSMC.2017.2662623 http://doi.org/10.1109/TSMC.2017.2662623 . .

H Azpúrua , , , GM Freitas , , , DG Macharet , , , 等 . . Multirobot coverage path planning using hexagonal segmentation for geophysical surveys . . Robotica , , 2018 . . 36 ( ( 8 ): ): 1144 - - 1166 . . DOI: 10.1017/S0263574718000292 http://doi.org/10.1017/S0263574718000292 . .

A Chakraborty , , , S Misra , , , R Sharma , , , 等 . . Observability conditions for switching sensing topology for cooperative localization . . Unmann Syst , , 2017 . . 5 ( ( 3 ): ): 141 - - 157 . . DOI: 10.1142/S2301385017400039 http://doi.org/10.1142/S2301385017400039 . .

H Choset . . Coverage for robotics-a survey of recent results . . Ann Math Artif Intell , , 2001 . . 31 ( ( 1-4 ): ): 113 - - 126 . . DOI: 10.1023/A:1016639210559 http://doi.org/10.1023/A:1016639210559 . .

MB Dias , , , R Zlot , , , N Kalra , , , 等 . . Market-based multirobot coordination:a survey and analysis . . Proc IEEE , , 2006 . . 94 ( ( 7 ): ): 1257 - - 1270 . . DOI: 10.1109/JPROC.2006.876939 http://doi.org/10.1109/JPROC.2006.876939 . .

C Di Franco , , , G Buttazzo . . Coverage path planning for UAVs photogrammetry with energy and resolution constraints . . J Intell Robot Syst , , 2016 . . 83 ( ( 3-4 ): ): 445 - - 462 . . DOI: 10.1007/s10846-016-0348-x http://doi.org/10.1007/s10846-016-0348-x . .

M Elango , , , S Nachiappan , , , MK Tiwari . . Balancing task allocation in multi-robot systems using K -means clustering and auction based mechanisms . . Expert Syst Appl , , 2011 . . 38 ( ( 6 ): ): 6486 - - 6491 . . DOI: 10.1016/j.eswa.2010.11.097 http://doi.org/10.1016/j.eswa.2010.11.097 . .

H Fang , , , SL Lu , , , J Chen , , , 等 . . Coalition formation based on a task-oriented collaborative ability vector . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 1 ): ): 139 - - 148 . . DOI: 10.1631/FITEE.1601608 http://doi.org/10.1631/FITEE.1601608 . .

Y Gabriely , , , E Rimon . . Spiral-STC:an on-line coverage algorithm of grid environments by a mobile robot . . Proc IEEE Int Conf on Robotics and Automation , , 2002 . . 954 - - 960 . . DOI: 10.1109/ROBOT.2002.1013479 http://doi.org/10.1109/ROBOT.2002.1013479 . .

Y Gabriely , , , E Rimon . . Competitive on-line coverage of grid environments by a mobile robot . . Comput Geom , , 2003 . . 24 ( ( 3 ): ): 197 - - 224 . . DOI: 10.1016/S0925-7721(02)00110-4 http://doi.org/10.1016/S0925-7721(02)00110-4 . .

E Galceran , , , M Carreras . . A survey on coverage path planning for robotics . . Robot Auton Syst , , 2013 . . 61 ( ( 12 ): ): 1258 - - 1276 . . DOI: 10.1016/j.robot.2013.09.004 http://doi.org/10.1016/j.robot.2013.09.004 . .

A Gautam , , , JK Murthy , , , G Kumar , , , 等 . . Cluster, allocate, cover:an efficient approach for multi-robot coverage . . Proc IEEE Int Conf on Systems, Man, and Cybernetics , , 2015 . . p.197 - - 203 . . DOI: 10.1109/SMC.2015.47 http://doi.org/10.1109/SMC.2015.47 . .

N Hazon , , , GA Kaminka . . On redundancy, efficiency, and robustness in coverage for multiple robots . . Robot Auton Syst , , 2008 . . 56 ( ( 12 ): ): 1102 - - 1114 . . DOI: 10.1016/j.robot.2008.01.006 http://doi.org/10.1016/j.robot.2008.01.006 . .

M Kapanoglu , , , M Alikalfa , , , M Ozkan , , , 等 . . A patternbased genetic algorithm for multi-robot coverage path planning minimizing completion time . . J Intell Manuf , , 2012 . . 23 ( ( 4 ): ): 1035 - - 1045 . . DOI: 10.1007/s10845-010-0404-5 http://doi.org/10.1007/s10845-010-0404-5 . .

AC Kapoutsis , , , SA Chatzichristofis , , , EB Kosmatopoulos . . DARP:divide areas algorithm for optimal multi-robot coverage path planning . . J Intell Robot Syst , , 2017 . . 86 ( ( 3-4 ): ): 663 - - 680 . . DOI: 10.1007/s10846-016-0461-x http://doi.org/10.1007/s10846-016-0461-x . .

N Karapetyan , , , K Benson , , , C McKinney , , , 等 . . Efficient multi-robot coverage of a known environment . . Proc IEEE/RSJ Int Conf on Intelligent Robots and Systems , , 2017 . . p.1846 - - 1852 . . DOI: 10.1109/IROS.2017.8206000 http://doi.org/10.1109/IROS.2017.8206000 . .

A Khamis , , , A Hussein , , , A Elmogy . . Multi-robot task allocation:a review of the state-of-the-art . . In:Koub$\hat a$a A, Martx$\mathop i\limits^\prime $nez-de Dios J (Eds.), Cooperative Robots and Sensor Networks 2015. Springer, Cham. , , 2015 . . DOI: 10.1007/978-3-319-18299-5_2 http://doi.org/10.1007/978-3-319-18299-5_2 . .

A Khan , , , I Noreen , , , Z Habib . . On complete coverage path planning algorithms for non-holonomic mobile robots: survey and challenges . . J Inform Sci Eng , , 2017 . . 33 ( ( 1 ): ): 101 - - 121 . . DOI: 10.6688/JISE.2017.33.1.7 http://doi.org/10.6688/JISE.2017.33.1.7 . .

Y Kong , , , MJ Zhang , , , DY Ye . . 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. , , 2016 . . DOI: 10.1007/978-3-319-30307-9_8 http://doi.org/10.1007/978-3-319-30307-9_8 . .

GS Li , , , WS Chou , , , F Yin . . Multi-robot coordinated exploration of indoor environments using semantic information . . Sci China Inform Sci , , 2018 . . 61 ( ( 7 ): ): 79201 DOI: 10.1007/s11432-017-9336-x http://doi.org/10.1007/s11432-017-9336-x . .

M Radmanesh , , , M Kumar , , , PH Guentert , , , 等 . . Overview of path-planning and obstacle avoidance algorithms for UAVs:a comparative study . . Unmann Syst , , 2018 . . 6 ( ( 2 ): ): 95 - - 118 . . DOI: 10.1142/S2301385018400022 http://doi.org/10.1142/S2301385018400022 . .

I Rekleitis , , , AP New , , , ES Rankin , , , 等 . . Efficient boustrophedon multi-robot coverage:an algorithmic approach . . Ann Math Artif Intell , , 2008 . . 52 ( ( 2-4 ): ): 109 - - 142 . . DOI: 10.1007/s10472-009-9120-2 http://doi.org/10.1007/s10472-009-9120-2 . .

J Tang , , , KJ Zhu , , , HX Guo , , , 等 . . Using auction-based task allocation scheme for simulation optimization of search and rescue in disaster relief . . Simul Model Pract Theor , , 2018 . . 82 132 - - 146 . . DOI: 10.1016/j.simpat.2017.12.014 http://doi.org/10.1016/j.simpat.2017.12.014 . .

B Xin , , , GQ Gao , , , YL Ding , , , 等 . . Distributed multirobot motion planning for cooperative multi-area coverage . . Proc 13th IEEE Int Conf on Control & Automation , , 2017 . . p.361 - - 366 . . DOI: 10.1109/ICCA.2017.8003087 http://doi.org/10.1109/ICCA.2017.8003087 . .

R Yehoshua , , , N Agmon , , , GA Kaminka . . Robotic adversarial coverage of known environments . . Int J Robot Res , , 2016 . . 35 ( ( 12 ): ): 1419 - - 1444 . . DOI: 10.1177/0278364915625785 http://doi.org/10.1177/0278364915625785 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰