Multi Objective Path Finding Based on Adding-Weight A* Algorithm


Article Preview

Multi-objective path planning is a path planning problem when there are more than one objective function to be optimized at the same time. This paper is based on traditional A* algorithm.To improve the algorithm A* and find out the shortest path in the different environments,we choose different weights and do global path planning by using improved evaluation function.We use the minimum binary heap in a linked list structure to manage the OPEN table,and the search efficiency has been improved.We compile the simulation program of path planning in the VC environment,then compare the operation time and generated paths by transforming the coordinates of the initial node and the goal node.Research shows that, the algorithm can improve the efficiency of the path planning efficiently.



Advanced Materials Research (Volumes 1079-1080)

Edited by:

Wen-Pei Sung and Jimmy (C.M.) Kao






Q. Wang et al., "Multi Objective Path Finding Based on Adding-Weight A* Algorithm", Advanced Materials Research, Vols. 1079-1080, pp. 711-715, 2015

Online since:

December 2014




* - Corresponding Author

[1] W. WEI,D.T. OUYANG,S. LU,Y.X. FENG. Multi objective path planning under dynamic uncertain environment[J]. Chinese Journal of Computers. 2011. 34(5): 836-837.

DOI: 10.3724/sp.j.1016.2011.00836

[2] CHABINI I, LAN SHAN. Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic network[J]. IEEE Transactions on Intelligent Transportation Systems, 2002, 3(1) : 60-74.

DOI: 10.1109/6979.994796

[3] KOENIG S, LIKHACHEV M, FURCY D. Lifelong planning A*[J]. Artificial Intelligence, 2004, 155(1-2): 93-146.

DOI: 10.1016/j.artint.2003.12.001

[4] SZCZERBA R J. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic System, 2000, 36(3): 869-878.

DOI: 10.1109/7.869506

[5] KOENIG S, LIKHACHEV M, YAXIN LIU, FURCY D. Incremental heuristic search in AI. AI Magazine, 2004, 25(2): 99–112.

[6] SEET B C, LIU Gen-ping, LEE Bu Sung, et al. A-STAR: A mobile ad hoc routing strategy for metropolis vehicular communications[C] /Networking Technologies, Services, and Protocols, Performance of Computer and Communication Networks, Mobile and Wireless Communications: Proceedings of the 3rd International IFIP-TC6 Networking conference (Networking'04), May 9-14, 2004, Athens, Greece. LNCS 3042. Berlin, Germany: Springer-Verlag, 2004: 989-999.

DOI: 10.1007/978-3-540-24693-0_81

[7] BELL M G H. Hyperstar: A multi-path A star algorithm for risk averse vehicle navigation[J]. Transportation Research, Part B , Methodological, 2009, 43(1): 97-107.

DOI: 10.1016/j.trb.2008.05.010

[8] Z.M. ZHAO,Z.D. MENG. Path planning of service mobile robot based on adding-weight A* algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2008(10): 197-198.

[9] S.X. LI,F. ZHU,J. ZHANG, et al. Multi constraint track planning using improved A* Algorithm[J]. Electronics Optics & Control , 2014, 21(7): 37-40.

In order to see related information, you need to Login.