Article
Auction-Based Consensus of Autonomous Vehicles for
Multi-Target Dynamic Task Allocation and Path Planning in an
Unknown Obstacle Environment
Wan-Yu Yu
1
, Xiao-Qiang Huang
2
, Hung-Yi Luo
1
, Von-Wun Soo
2
and Yung-Lung Lee
3,
*
Citation: Yu, W.-Y.; Huang, X.-Q.;
Luo, H.-Y.; Soo, V.-W.; Lee, Y.-L.
Auction-Based Consensus of
Autonomous Vehicles for
Multi-Target Dynamic Task
Allocation and Path Planning in an
Unknown Obstacle Environment.
Appl. Sci. 2021, 11, 5057. https://
doi.org/10.3390/app11115057
Academic Editor: Javier Alonso Ruiz
Received: 4 May 2021
Accepted: 27 May 2021
Published: 30 May 2021
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2021 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
1
Institute of Information Systems and Applications, National Tsing Hua University, 101, Section 2,
Kuang-Fu Road, Hsinchu 30043, Taiwan; s9865804@m98.nthu.edu.tw (W.-Y.Y.);
sai28055707@gmail.com (H.-Y.L.)
2
Department of Computer Science, National Tsing Hua University, 101, Section 2, Kuang-Fu Road,
Hsinchu 30043, Taiwan; xqhuang718@gmail.com (X.-Q.H.); soo@cs.nthu.edu.tw (V.-W.S.)
3
Department of Power Vehicle and Systems Engineering, Chung Cheng Institute of Technology, National
Defense University, No. 75, Shiyuan Rd., Dashi Jen 335, Taoyuan, Taiwan
* Correspondence: yunglunglee84@ccit.ndu.edu.tw
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.
Keywords:
autonomous vehicles; consensus decision making; task reallocation; team formation;
obstacle avoidance path planning; auction mechanism
1. Introduction
The global market of using autonomous vehicles has grown substantially in recent
years and has become an important tool for commercial, government and consumer applica-
tions. It can support solutions in many fields and is widely used in construction, oil, natural
gas, energy, agriculture, military and other fields. Autonomous Vehicle applications have
expanded from the traditional ground-based collection and delivery problem extends to
air, underwater even to space applications. Potential applications for autonomous vehicle
systems include space-based interferometers, military mission execution [
1
] (i.e., com-
bat, surveillance and reconnaissance systems), hazardous material handling, distributed
re-configurable sensor networks [
2
]. The operation of autonomous vehicle has also been ad-
vanced from single vehicle to multi-vehicle systems in the field. The coordination between
autonomous vehicles becomes a challenging issue for multi-vehicle systems during opera-
tion. In the autonomous vehicle operations, there are tasks in controlling the movement
situation such as dynamic path planning, mission planning, multiple obstacle avoidance
and task coordination among vehicles in response to the state and environmental changes.
These tasks become more complex and interesting since the dynamic and unknown envi-
ronment can make the autonomous coordination among vehicles even more demanding
and challenging to achieve.
In this work, we treat the autonomous multi-vehicle team as a Multi-agent System
(MAS) and thus the terms “autonomous vehicle” and “agent” may be used interchangeably
Appl. Sci. 2021, 11, 5057. https://doi.org/10.3390/app11115057 https://www.mdpi.com/journal/applsci
