Anytime Dynamic Heuristic Search for Suboptimal Solution on Path Search

被引:0
|
作者
Kong, Ru [1 ]
Tong, Xiangrong [1 ]
机构
[1] Yantai Univ, Sch Comp & Control Engn, Yantai, Shandong, Peoples R China
来源
2020 13TH INTERNATIONAL CONGRESS ON IMAGE AND SIGNAL PROCESSING, BIOMEDICAL ENGINEERING AND INFORMATICS (CISP-BMEI 2020) | 2020年
基金
中国国家自然科学基金;
关键词
path search; bounded-cost search; heuristic search; suboptimal solution;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Path search is designed to find a path by traversing the state spaces from the initial state to the target state. Given enough memory and run time, the A* algorithm can find an optimal solution, but it expends much time to distinguish similar paths. Therefore, many scholars have proposed variants of the A" algorithm that find a suboptimal solution to speed up the searching efficiency. In this paper, the A* algorithm is improved and a new anytime dynamic heuristic search algorithm (ADHS) is proposed. It can find a solution quickly and then continuously optimize the quality of the solution to find the suboptimal solution until the end of time. The ADHS includes two stages, in the exploration stage, given an arbitrary cost bound, the solution is quickly obtained; in the update stage, where no setting parameters are required, reuses the previous search results. According to the cost of the latest solution, the dynamic weight factor w is introduced, which is half of the error between the current cost bound and the current solution. The next cost bound is dynamically adjusted, and the suboptimal solution is output. We tested the performance of the ADHS on the grid maps, and the experiments demonstrated that the performance of the ADHS was better than other algorithms.
引用
收藏
页码:1070 / 1074
页数:5
相关论文
共 50 条
  • [1] Anytime heuristic search
    Hansen, Eric A.
    Zhou, Rong
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2007, 28 : 267 - 297
  • [2] Anytime search in dynamic graphs
    Likhachev, Maxim
    Ferguson, Dave
    Gordon, Geoff
    Stentz, Anthony
    Thrun, Sebastian
    ARTIFICIAL INTELLIGENCE, 2008, 172 (14) : 1613 - 1643
  • [3] Anytime heuristic search for partial satisfaction planning
    Benton, J.
    Do, Minh
    Kambhampati, Subbarao
    ARTIFICIAL INTELLIGENCE, 2009, 173 (5-6) : 562 - 592
  • [4] Probably bounded suboptimal heuristic search
    Stern, Roni
    Dreiman, Gal
    Valenzano, Richard
    ARTIFICIAL INTELLIGENCE, 2019, 267 : 39 - 57
  • [5] A dynamic bidirectional heuristic trust path search algorithm
    Che, Jiaying
    Tong, Xiangrong
    Yu, Lei
    CAAI TRANSACTIONS ON INTELLIGENCE TECHNOLOGY, 2022, 7 (03) : 340 - 353
  • [6] Dynamic Weighted Heuristic Trust Path Search Algorithm
    Kong, Ru
    Tong, Xiangrong
    IEEE ACCESS, 2020, 8 : 157382 - 157390
  • [7] AWA* - A Window Constrained Anytime Heuristic Search Algorithm
    Aine, Sandip
    Chakrabarti, P. P.
    Kumar, Rajeev
    20TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2007, : 2250 - 2255
  • [8] A*-Connect: Bounded Suboptimal Bidirectional Heuristic Search
    Islam, Fahad
    Narayanan, Venkatraman
    Likhachev, Maxim
    2016 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), 2016, : 2752 - 2758
  • [9] X*: Anytime Multiagent Path Planning With Bounded Search
    Vedder, Kyle
    Biswas, Joydeep
    AAMAS '19: PROCEEDINGS OF THE 18TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, 2019, : 2247 - 2249
  • [10] Aggressive Heuristic Search for Sub-Optimal Solution on Path Planning
    Liu, Junjun
    Li, Wenzheng
    2018 8TH INTERNATIONAL CONFERENCE ON ELECTRONICS INFORMATION AND EMERGENCY COMMUNICATION (ICEIEC), 2018, : 16 - 20