Journal
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
Volume 23, Issue 4, Pages 617-631Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TEVC.2018.2878221
Keywords
A* search; ant colony optimization (ACO); autonomous underwater vehicles (AUVs); dense obstacles; path planning
Funding
- National Natural Science Foundation of China [61622206, 61332002, 61873097]
- Natural Science Foundation of Guangdong [2015A030306024]
Ask authors/readers for more resources
Path planning is one of the most important problems in the development of autonomous underwater vehicles (AUVs). In some common AUV missions, e.g., wreckage search for rescue, an AUV is often required to traverse multiple targets in a complex environment with dense obstacles. In such case, the AUV path planning problem becomes even more challenging. In order to address the problem, this paper develops a two-layer algorithm, namely ACO-A*, by combining the ant colony optimization (ACO) with the A* search. Once a mission with a set of arbitrary targets is assigned, ACO is responsible to determine the traveling order of targets. But, prior to ACO, a cost graph indicating the necessary traveling costs among targets must be quickly established to facilitate traveling order evaluation. For this purpose, a coarse-grained modeling with a representative-based estimation (RBE) strategy is proposed. Following the order obtained by ACO, targets will be traversed one by one and the pairwise path planning to reach each target can be performed during vehicle driving. To deal with the dense obstacles, A* is adopted to plan paths based on a fine-grained modeling and an admissible heuristic function is designed for A* to guarantee its optimality. Experiments on both synthetic and realistic scenarios have been designed to validate the efficiency of the proposed ACO-A*, as well as the effectiveness of RBE and the necessity of A*.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available