A* algorithm based on random walk

• Engineering and Technology • Previous Articles

A* algorithm based on random walk

LIU Haohan¹, GUO Jingjing¹, LI Jianfu¹, FENG Mei², HE Huaiqing¹

(1. College of Computer Science and Technology, CAUC, Tianjin 300300, China;2. North Regional Air Traffic Management Bureau of CAAC, Beijing 100621, China)

Received:2017-02-23 Revised:2017-03-27 Online:2017-12-27 Published:2017-12-15

Abstract

Abstract: A* algorithm based on random walk combining with Monte-Carlo random walk is proposed to solve the plateau exploration in A* algorithm. When the A* algorithm falls into the plateau exploration, a random walk algorithm is employed to help it escape from the plateaus. In addition, a new method is proposed to test plateau exploration.The phenomenon is named plateau exploration as it continuously expand states n times without reducing the heuristic value compared with last states'expanded on last expansion. Experimental results prove the effectiveness of the improved A* algorithm.

Key words: shortest path, heuristic search, A* algorithm, plateau exploration, Monte-Carlo random walk

CLC Number:

TP301

LIU Haohan, GUO Jingjing, LI Jianfu, FENG Mei, HE Huaiqing. A* algorithm based on random walk[J]. .

References

[1] 胡欣, 徐涛,丁晓璐,等.国际航线网络中K条最短路径算法改进与仿真[J].计算机应用, 2014, 34(4): 1192-1195.
[2] DECHTER R, PEARL J. Generalized best-first search strategies and the optimality of A* [J]. Journal of the ACM, 1985, 32(3): 505-536.
[3] 吕强.面向高性能和表达力的自动规划[D].合肥:中国科学技术大学, 2012.
[4] HELMERT M, ROGER G. How Good is Almost Perpect[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2008: 944-949.
[5] HAMPSON S, KIBLER D. Plateaus and Plateau Search in Boolean Satisfiability Problems: When to Give Up Searching and Start Again[C]//In the 2nd DIMACS Implementation Challenge, 1993: 437-456.
[6] FRANK J D, CHEESEMAN P, STUTZ J. When gravity fails: local search topology[J]. Journal of Artificial Intelligence Research, 1997(12):249-281.
[7] HOFFMANN J. Local Search Topology in Planning Benchmarks: An Empirical Analysis[C]//Proceedings of the International Joint Conference on Artificial Intelligence, 2001: 453-458.
[8] HOFFMANN J. Local Search Topology in Planning Benchmarks: A Theoretical Analysis[C]//Proceedings of the International Conference on AI Planning and Scheduling, 2002: 92-100.
[9] BENTONJ, TALAMADUPULAK,EYERICHP, et al.G-ValuePlateaus:Challenge for Planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling, 2010: 259-262.
[10] GOVER F, LAGUNA M. Tabu Search[M]. Boston: Kluwer Academic Publishers, 1997.
[11] KAUTZ H, SEMAN B. Pushing the Envelope: Planning, Propositional Logic and Stochastic Search[C]//Proceedings of the AAAI Coference on Aritifical Intelligence, 1996: 1194-1201.
[12] NAKHOST H, MSLLER M. Monte-Carlo Exploration for Deterministic Planning[C]//IJCAI, 2009: 1766-1771.
[13] NAKHOSTH, HOFFMANNJ,MULLERM. ResourceConstrainedPlanning:A Monte Carlo Random Walk Approach [C]//Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling (ICAPS-2012), 2012: 181-189.
[14] LU Qiang, XU You, HUANG Ruoyun, et al. The Roamer Planner Random-Walk Assisted Best-First Search[C]//The 2011 International Planning Competition, 2011: 73-76.
[15] NAKHOST H, MULLER M, VALENZANO R, et al. Arvand: The Art of RandomWalks[C]//The 2011 International Planning Competition, 2011:15-16.