ANYTIME RECTANGLE EXPANSION A* ALGORITHM FOR TIME-LIMITED PATHFINDING

An Zhang, Chong Li, and Wenhao Bi

References

  1. [1] J. Zhong and J. Su, Robot path planning in narrow passagesbased on probabilistic roadmaps, International Journal ofRobotics and Automation, 28(3), 2013, 207–217.
  2. [2] S.M. Persson and I Sharf, Sampling-based A algorithm forrobot path-planning, International Journal of Robotics Re-search, 33(13), 2014, 1683–1708.
  3. [3] M. Alajlan, I. Chaari, A. Koubaa, et al., Global robot pathplanning using GA for large grid maps: modelling, performanceand experimentation, International Journal of Robotics andAutomation, 31(6), 2016, 484–495.
  4. [4] P. Nguyen, T. Crainic, and M. Toulouse, A tabu search fortime-dependent multi-zone multi-trip vehicle routing problemwith time windows, European Journal of Operational Research,231(1), 2013, 43–56.
  5. [5] C. Hernandez and J. Baier, Avoiding and escaping depressionsin real-time heuristic search, Journal Of Artificial IntelligenceResearch, 43(1), 2014, 523–570.
  6. [6] J. Ni, K. Wang, Q. Cao, Z. Khan, and X. Fan, A memeticalgorithm with variable length chromosome for robot pathplanning under dynamic environments, International Journalof Robotics and Automation, 32(4), 2017, 414–424.
  7. [7] N. Flerova, R. Marinescu, and R. Dechter, Weighted heuristicanytime search: new schemes for optimization over graphicalmodels, Annals of Mathematics & Artificial Intelligence, 79(1),2017, 77–128.
  8. [8] E. Hansen and R. Zhou, Anytime heuristic search, Journal ofArtificial Intelligence Research, 28(28), 2007, 267–297.
  9. [9] R. Zhou and E.A. Hansen, Multiple sequence alignment usinganytime A, Eighteenth National Conf. on Artificial Intelligence and Fourteenth Conf. on Innovative Applications ofArtificial Intelligence, Edmonton, Alta, Canada, 2002, 60–69.
  10. [10] S. Aine, P. Chakrabarti, and R. Kumar, AWA – A windowconstrained anytime heuristic search algorithm, Proc. of theInt. Joint Conf. on Artificial Intelligence, Hyderabad, India,2007, 2250–2255.
  11. [11] S.G. Vadlamudi, S. Aine, and P. Chakrabarti, A memory-bounded anytime heuristic-search algorithm, IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics,41(3), 2011, 725–735.
  12. [12] A. Hornung, A. Dornbush, M. Likhachev, et al., Anytimesearch-based footstep planning with suboptimality bounds,IEEE-RAS Int. Conf. on Humanoid Robots, Osaka, Japan,2012, 674–679.
  13. [13] M. Likhachev, G.J. Gordon, and S. Thrun, ARA: Anytime Awith provable bounds on sub-optimality, Proc. of 2003 Advancesin Neural Information Processing Systems, Vancouver, BC,Canada, 2003.
  14. [14] J.V.D. Berg, R. Shah, A. Huang, and K. Goldberg, ANA:anytime nonparametric A, Proc. of the Twenty-Fifth AAAIConf. on Artificial Intelligence, San Francisco, CA, Unitedstates, 2011, 105–111.
  15. [15] X. Sun, T. Uras, S. Koenig, and W. Yeoh, Incremental ARA:An incremental anytime search algorithm for moving-targetsearch, Proc. of the Twenty-Second International Conferenceon Automated Planning and Scheduling, Atibaia, Sao Paulo,Brazil, 2012, 243–251.
  16. [16] P.E. Hart, N.J. Nilsson, and B. Raphael, A formal basis forthe heuristic determination of minimum cost paths, IEEETransactions on Systems Science and Cybernetics, 4(2), 1968,100–107.
  17. [17] A. Zhang, C. Li, and W. Bi, Rectangle expansion A∗ pathfinding for grid maps, Chinese Journal of Aeronautics, 29(5), 2016,1385–1396.
  18. [18] N.R. Sturtevant, The grid-based path planning competition,AI Magazine, 35(3), 2014, 66–69.
  19. [19] N.R. Sturtevant, Benchmarks for grid-based pathfinding, IEEETransactions on Computational Intelligence and AI in Games,4(2), 2012,144–148.
  20. [20] D. Harabor and A. Botea. Breaking path symmetries on 4-connected grid maps, AAAI Conf. on Artificial Intelligenceand Interactive Digital Entertainment, Stanford, CA, Unitedstates, 2010, 33–38.
  21. [21] D. Harabor, Graph pruning and symmetry breaking on gridmaps, Proc. of the Int. Joint Conference on Artificial Intelligence, Barcelona, Barcelona, Catalonia, Spain, 2011, 2816–2817.
  22. [22] K. Xiao, C. Gao, X. Hu, et al., Improved Theta: Improvedany-angle path planning on girds, Journal of ComputationalInformation Systems, 10(20), 2014, 8881–8890.
  23. [23] E. Burns, W. Ruml, and M. B. Do, Heuristic search when timematters, Journal of Artificial Intelligence Research, 47(47),2013, 697–740.

Important Links:

Go Back