An Improved A∗ Algorithm for UAV Path Planning Problems

Jinchao Chen; Mengyuan Li; Zhenyu Yuan; Qing Gu

doi:10.1109/ITNEC48623.2020.9084806

An Improved A∗ Algorithm for UAV Path Planning Problems

Jinchao Chen, Mengyuan Li, Zhenyu Yuan, Qing Gu

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

49 Scopus citations

Abstract

Recently unmanned aerial vehicle (UAV) has been widely applied in military and civil fields due to its strong autonomic and adaptability. Compared with the manned vehicles, UAV has significant advantages in carrying out the dangerous work by keeping human life away from risks. Although UAV provides notable benefits to practical applications, it gives rise to a complex path planning problem. The optimal flying path of a UAV should be obtained such that the flight length and time cost can be reduced as much as possible. In this paper, we study the path planning problem and propose an improved A∗ algorithm to solve the problem. First, with the models of UAVs and regions, an exact formulation based on mixed integer linear programming (MILP) is introduced to completely search the solution space. Then, by improving the evaluation function and the node selection strategy, an improved A∗ algorithm is presented to produce an optimal flight path for UAVs. Experimental results show that the approach proposed is more effective to solve the path planning problem than the traditional algorithms.

Original language	English
Title of host publication	Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020
Editors	Bing Xu, Kefen Mou
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	958-962
Number of pages	5
ISBN (Electronic)	9781728143903
DOIs	https://doi.org/10.1109/ITNEC48623.2020.9084806
State	Published - Jun 2020
Event	4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020 - Chongqing, China Duration: 12 Jun 2020 → 14 Jun 2020

Publication series

Name	Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

Conference

Conference	4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020
Country/Territory	China
City	Chongqing
Period	12/06/20 → 14/06/20

Keywords

A
algorithm
node selection strategy
path planing
unmanned aerial vehicle

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1109/ITNEC48623.2020.9084806

Cite this

Chen, J., Li, M., Yuan, Z., & Gu, Q. (2020). An Improved A∗ Algorithm for UAV Path Planning Problems. In B. Xu, & K. Mou (Eds.), Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020 (pp. 958-962). Article 9084806 (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITNEC48623.2020.9084806

Chen, Jinchao ; Li, Mengyuan ; Yuan, Zhenyu et al. / An Improved A∗ Algorithm for UAV Path Planning Problems. Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020. editor / Bing Xu ; Kefen Mou. Institute of Electrical and Electronics Engineers Inc., 2020. pp. 958-962 (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020).

@inproceedings{199f6708d9a145b7b626cc6c5acbcf57,

title = "An Improved A∗ Algorithm for UAV Path Planning Problems",

abstract = "Recently unmanned aerial vehicle (UAV) has been widely applied in military and civil fields due to its strong autonomic and adaptability. Compared with the manned vehicles, UAV has significant advantages in carrying out the dangerous work by keeping human life away from risks. Although UAV provides notable benefits to practical applications, it gives rise to a complex path planning problem. The optimal flying path of a UAV should be obtained such that the flight length and time cost can be reduced as much as possible. In this paper, we study the path planning problem and propose an improved A∗ algorithm to solve the problem. First, with the models of UAVs and regions, an exact formulation based on mixed integer linear programming (MILP) is introduced to completely search the solution space. Then, by improving the evaluation function and the node selection strategy, an improved A∗ algorithm is presented to produce an optimal flight path for UAVs. Experimental results show that the approach proposed is more effective to solve the path planning problem than the traditional algorithms.",

keywords = "A, algorithm, node selection strategy, path planing, unmanned aerial vehicle",

author = "Jinchao Chen and Mengyuan Li and Zhenyu Yuan and Qing Gu",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020 ; Conference date: 12-06-2020 Through 14-06-2020",

year = "2020",

month = jun,

doi = "10.1109/ITNEC48623.2020.9084806",

language = "英语",

series = "Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "958--962",

editor = "Bing Xu and Kefen Mou",

booktitle = "Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020",

}

Chen, J, Li, M, Yuan, Z & Gu, Q 2020, An Improved A∗ Algorithm for UAV Path Planning Problems. in B Xu & K Mou (eds), Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020., 9084806, Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020, Institute of Electrical and Electronics Engineers Inc., pp. 958-962, 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020, Chongqing, China, 12/06/20. https://doi.org/10.1109/ITNEC48623.2020.9084806

An Improved A∗ Algorithm for UAV Path Planning Problems. / Chen, Jinchao; Li, Mengyuan; Yuan, Zhenyu et al.
Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020. ed. / Bing Xu; Kefen Mou. Institute of Electrical and Electronics Engineers Inc., 2020. p. 958-962 9084806 (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Improved A∗ Algorithm for UAV Path Planning Problems

AU - Chen, Jinchao

AU - Li, Mengyuan

AU - Yuan, Zhenyu

AU - Gu, Qing

PY - 2020/6

Y1 - 2020/6

N2 - Recently unmanned aerial vehicle (UAV) has been widely applied in military and civil fields due to its strong autonomic and adaptability. Compared with the manned vehicles, UAV has significant advantages in carrying out the dangerous work by keeping human life away from risks. Although UAV provides notable benefits to practical applications, it gives rise to a complex path planning problem. The optimal flying path of a UAV should be obtained such that the flight length and time cost can be reduced as much as possible. In this paper, we study the path planning problem and propose an improved A∗ algorithm to solve the problem. First, with the models of UAVs and regions, an exact formulation based on mixed integer linear programming (MILP) is introduced to completely search the solution space. Then, by improving the evaluation function and the node selection strategy, an improved A∗ algorithm is presented to produce an optimal flight path for UAVs. Experimental results show that the approach proposed is more effective to solve the path planning problem than the traditional algorithms.

AB - Recently unmanned aerial vehicle (UAV) has been widely applied in military and civil fields due to its strong autonomic and adaptability. Compared with the manned vehicles, UAV has significant advantages in carrying out the dangerous work by keeping human life away from risks. Although UAV provides notable benefits to practical applications, it gives rise to a complex path planning problem. The optimal flying path of a UAV should be obtained such that the flight length and time cost can be reduced as much as possible. In this paper, we study the path planning problem and propose an improved A∗ algorithm to solve the problem. First, with the models of UAVs and regions, an exact formulation based on mixed integer linear programming (MILP) is introduced to completely search the solution space. Then, by improving the evaluation function and the node selection strategy, an improved A∗ algorithm is presented to produce an optimal flight path for UAVs. Experimental results show that the approach proposed is more effective to solve the path planning problem than the traditional algorithms.

KW - A

KW - algorithm

KW - node selection strategy

KW - path planing

KW - unmanned aerial vehicle

UR - http://www.scopus.com/inward/record.url?scp=85086277803&partnerID=8YFLogxK

U2 - 10.1109/ITNEC48623.2020.9084806

DO - 10.1109/ITNEC48623.2020.9084806

M3 - 会议稿件

AN - SCOPUS:85086277803

T3 - Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

SP - 958

EP - 962

BT - Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

A2 - Xu, Bing

A2 - Mou, Kefen

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

Y2 - 12 June 2020 through 14 June 2020

ER -

Chen J, Li M, Yuan Z, Gu Q. An Improved A∗ Algorithm for UAV Path Planning Problems. In Xu B, Mou K, editors, Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020. Institute of Electrical and Electronics Engineers Inc. 2020. p. 958-962. 9084806. (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020). doi: 10.1109/ITNEC48623.2020.9084806

An Improved A∗ Algorithm for UAV Path Planning Problems

Abstract

Publication series

Conference

Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this