Auction-Based Consensus of Autonomous Vehicles for Multi-Target Dynamic Task Allocation and Path Planning in an Unknown Obstacle Environment
Source abstract
Abstract
The autonomous vehicle technology has recently been developed rapidly in a wide variety of applications. However, coordinating a team of autonomous vehicles to complete missions in an unknown and changing environment has been a challenging and complicated task. We modify the consensus-based auction algorithm (CBAA) so that it can dynamically reallocate tasks among autonomous vehicles that can flexibly find a path to reach multiple dynamic targets while avoiding unexpected obstacles and staying close as a group as possible simultaneously. We propose the core algorithms and simulate with many scenarios empirically to illustrate how the proposed framework works. Specifically, we show that how autonomous vehicles could reallocate the tasks among each other in finding dynamically changing paths while certain targets may appear and disappear during the movement mission. We also discuss some challenging problems as a future work.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Distributed Control Multi-Agent Systems · Transportation and Mobility Innovations
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Institute of Information Systems and Applications, National Tsing Hua University, 101, Section 2, Kuang-Fu Road, Hsinchu 30043, Taiwan
Department of Computer Science, National Tsing Hua University, 101, Section 2, Kuang-Fu Road, Hsinchu 30043, Taiwan
Department of Power Vehicle and Systems Engineering, Chung Cheng Institute of Technology, National Defense University, No. 75, Shiyuan Rd., Dashi Jen 335, Taoyuan, Taiwan
References (39)
Show source-provided references
1. Design challenges of multi-UAV systems in cyber-physical applications: A comprehensive survey and future directions10.1109/COMST.2019.2924143 ↗
2. Information consensus in multivehicle cooperative control10.1109/MCS.2007.338264 ↗
3. Multi-robot task allocation: A review of the state-of-the-art
4. Thibbotuwawa, A., Nielsen, P., Bocewicz, G., and Banaszak, Z. (2019). UAVs Fleet Mission Planning Subject to Weather Fore-Cast and Energy Consumption Constraints. Conference on Automation, Springer.10.1007/978-3-030-13273-6_11 ↗
5. Jones, H.L., Rock, S.M., Burns, D., and Morris, S. (2002, January 9–11). Autonomous robots in swat applications: Research, design, and operations challenges. Proceedings of the 2002 Symposium for the Association of Unmanned Vehicle Systems International, AUVSI’02, Orlando, FL, USA.
6. Scherer, J., Yahyanejad, S., Hayat, S., Yanmaz, E., Andre, T., Khan, A., Vukadinovic, V., Bettstetter, C., Hellwagner, H., and Rinner, B. (2015, January 18). An autonomous multi-UAV system for search and rescue. Proceedings of the First Workshop on Micro Aerial Vehicle Networks, Systems, and Applications for Civilian Use, Florence, Italy.10.1145/2750675.2750683 ↗
7. Zear, A., and Ranga, V. (2020). Path Planning of Unmanned Aerial Vehicles: Current State and Future Challenges. First International Conference on Sustainable Technologies for Computational Intelligence, Springer.10.1007/978-981-15-0029-9_32 ↗
8. Cutello, V., Nicosia, G., and Pavone, M. (2004). Exploring the Capability of Immune Algorithms: A Characterization of Hypermutation Operators. International Conference on Artificial Immune Systems, Springer.10.1007/978-3-540-30220-9_22 ↗
9. Hybrid particle swarm optimization and genetic algorithm for multi-UAV formation reconfiguration10.1109/MCI.2013.2264577 ↗
10. Kothari, M., Postlethwaite, I., and Gu, D.W. (2009, January 15–18). Multi-UAV path planning in obstacle rich environments using rapidly-exploring random trees. Proceedings of the 48th IEEE Conference on Decision and Control (CDC) Held Jointly with 2009 28th Chinese Control Conference, Shanghai, China.10.1109/CDC.2009.5400108 ↗
11. Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization10.1109/TIP.2019.2963378 ↗
12. A model of the formation of fish schools and migrations of fish10.1016/j.ecolmodel.2003.06.006 ↗
13. The dynamic window approach to collision avoidance10.1109/100.580977 ↗
14. Consensus-based decentralized auctions for robust task allocation10.1109/TRO.2009.2022423 ↗
15. Argyle, M., Casbeer, D.W., and Beard, R. (July, January 29). A multi-team extension of the consensus-based bundle algorithm. Proceedings of the 2011 American Control Conference, San Francisco, CA, USA.10.1109/ACC.2011.5991162 ↗
16. Honorable Kevin, M., and Fahey, M.J. (2018, August 28). Unmanned Systems Integrated Roadmap 2017–2042. Available online: https://www.defensedaily.com/wp-content/uploads/post_attachment/206477.pdf.
17. U.S. General Services Administration Office of Citizen Services and Innovative Technologies (2021, May 27). Unmanned Aircraft Systems Roadmap 2005–2030. Available online: https://fas.org/irp/program/collect/uav_roadmap2005.pdf.
18. Gerkey, B.P., and Mataric, M.J. (2003). A framework for studying multi-robot task allocation. Multi-Robot Systems: From Swarms to Intelligent Automata, Volume II, Springer.
19. A comprehensive taxonomy for multi-robot task allocation10.1177/0278364913496484 ↗
20. Lemaire, T., Alami, R., and Lacroix, S. (May, January 26). A distributed tasks allocation scheme in multi-UAV context. Proceedings of the IEEE International Conference on Robotics and Automation, ICRA’04, New Orleans, LA, USA.
21. Brunet, L., Choi, H.L., and How, J. (2008, January 18–21). Consensus-based auction approaches for decentralized task assignment. Proceedings of the AIAA Guidance, Navigation and Control Conference and Exhibit, Honolulu, HI, USA.10.2514/6.2008-6839 ↗
22. Smith, D., Wetherall, J., Woodhead, S., and Adekunle, A. (2014, January 12–14). A cluster-based approach to consensus based distributed task allocation. Proceedings of the 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Torino, Italy.10.1109/PDP.2014.87 ↗
23. Wang, S., Shi, D., Dong, Y., and Kuang, H. (2020, January 14–16). Research on Distributed Task Allocation of Loitering Munition Swarm. Proceedings of the 2020 International Conference on Information Science, Parallel and Distributed Systems (ISPDS), Xi’an, China.10.1109/ISPDS51347.2020.00041 ↗
24. Behavior-based formation control for multirobot teams10.1109/70.736776 ↗
25. A decentralized approach to formation maneuvers10.1109/TRA.2003.819598 ↗
26. Bithas, P.S., Michailidis, E.T., Nomikos, N., Vouyioukas, D., and Kanatas, A.G. (2019). A survey on machine-learning techniques for UAV-based communications. Sensors, 19.10.3390/s19235170 ↗
27. Leader-to-formation stability10.1109/TRA.2004.825275 ↗
28. A General Algorithm for Robot Formations Using Local Sensing and Minimal Communication10.1109/TRA.2002.803458 ↗
29. Luo, D., Xu, W., Wu, S., and Ma, Y. (2013, January 26–28). UAV formation flight control and formation switch strategy. Proceedings of the 2013 8th International Conference on Computer Science & Education, Colombo, Sri Lanka.
30. A coordination architecture for spacecraft formation control10.1109/87.960341 ↗
31. A decentralized cooperative control scheme with obstacle avoidance for a team of mobile robots10.1109/TIE.2013.2245612 ↗
32. Consensus strategies for cooperative control of vehicle formations10.1049/iet-cta:20050401 ↗
33. Baranzadeh, A., and Nazarzehi, V. (2015, January 6–9). A decentralized formation building algorithm with obstacle avoidance for multi-robot systems. Proceedings of the 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), Zhuhai, China.10.1109/ROBIO.2015.7419717 ↗
34. Theory and experiment on formation-containment control of multiple multirotor unmanned aerial vehicle systems10.1109/TASE.2018.2792327 ↗
35. Alonso-Mora, J., Montijano, E., Schwager, M., and Rus, D. (2016, January 16–21). Distributed multi-robot formation control among obstacles: A geometric and optimization approach with consensus. Proceedings of the 2016 IEEE International Conference on Robotics and Automation (ICRA), Stockholm, Sweden.10.1109/ICRA.2016.7487747 ↗
36. Zhu, H., Juhl, J., Ferranti, L., and Alonso-Mora, J. (2019, January 20–24). Distributed multi-robot formation splitting and merging in dynamic environments. Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada.10.1109/ICRA.2019.8793765 ↗
37. Min, H., Sun, F., and Niu, F. (2009, January 11–13). Decentralized UAV formation tracking flight control using gyroscopic force. Proceedings of the 2009 IEEE International Conference on Computational Intelligence for Measurement Systems and Applications, Hong Kong, China.
38. A multi-objective exploration strategy for mobile robots under operational constraints10.1109/ACCESS.2013.2283031 ↗
39. US ballistic missile defenses, 201910.1080/00963402.2019.1680055 ↗