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 条
  • [21] Anytime heuristic search in temporal HTN planning for developing incident action plans
    Tang, Pan
    Wang, Hongwei
    Qi, Chao
    Wang, Jian
    AI COMMUNICATIONS, 2012, 25 (04) : 321 - 342
  • [22] Weighted heuristic anytime search: new schemes for optimization over graphical models
    Natalia Flerova
    Radu Marinescu
    Rina Dechter
    Annals of Mathematics and Artificial Intelligence, 2017, 79 : 77 - 128
  • [23] Anytime, dynamic planning in high-dimensional search spaces
    Ferguson, Dave
    Stentz, Anthony
    PROCEEDINGS OF THE 2007 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-10, 2007, : 1310 - +
  • [24] A TECHNOLOGICAL SYSTEM FOR THE HEURISTIC-SEARCH FOR A SOLUTION
    GERMAN, OV
    GERMANOVICH, EI
    JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL, 1995, 33 (03) : 149 - 156
  • [25] Local search guided by path relinking and heuristic bounds
    Pasia, Joseph M.
    Gandibleux, Xavier
    Doerner, Karl F.
    Hartl, Richard F.
    EVOLUTIONARY MULTI-CRITERION OPTIMIZATION, PROCEEDINGS, 2007, 4403 : 501 - +
  • [26] On-line path planning by heuristic hierarchical search
    Henrich, D
    Wurll, C
    Worn, H
    IECON '98 - PROCEEDINGS OF THE 24TH ANNUAL CONFERENCE OF THE IEEE INDUSTRIAL ELECTRONICS SOCIETY, VOLS 1-4, 1998, : 2239 - 2244
  • [27] GSST: anytime guaranteed search
    Geoffrey Hollinger
    Athanasios Kehagias
    Sanjiv Singh
    Autonomous Robots, 2010, 29 : 99 - 118
  • [28] GSST: anytime guaranteed search
    Hollinger, Geoffrey
    Kehagias, Athanasios
    Singh, Sanjiv
    AUTONOMOUS ROBOTS, 2010, 29 (01) : 99 - 118
  • [29] Anytime Focal Search with Applications
    Cohen, Liron
    Greco, Matias
    Ma, Hang
    Hernandez, Carlos
    Felner, Ariel
    Kumar, T. K. Satish
    Koenig, Sven
    PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2018, : 1434 - 1441
  • [30] Dynamic improvements of heuristic evaluations during search
    Kainz, G
    Kaindl, H
    PROCEEDINGS OF THE THIRTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE EIGHTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE, VOLS 1 AND 2, 1996, : 311 - 317