微信服务号

微信订阅号

2025-4-3- 18
Home > Archive>Volume 20, Issue 9, 2009 >2352-2365
PDF HTML XML Export Cite reminder
BDD-Based Incremental Heuristic Search
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [23]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Incremental search reuses information from previous searches to find solutions to a series of similar search problems. It is potentially faster than solving each search problem from scratch. This is very important because many artificial intelligence systems have to adapt their plans continuously to changes in the world. If the changes are small, incremental search will be very efficient. BDD (binary decision diagram)-Based heuristic search combines the advantages of BDD-based search and heuristic search. Heuristic search impacts the size of the resulting search trees and BDDs can be used to efficiently describe the sets of states based on their binary encodings. This article first introduces BDD-based heuristic search and incremental search. Combining the two methods, it then gives a BDD-based incremental heuristic search algorithm BDDRPA*. The experimental results show that BDDRPA* is a very efficient incremental heuristic search algorithm. It can be used to solve many problems like symbolic replanning and robot navigation problems and so on.

    Reference
    [1] desJardins M, Durfee E, Ortiz C, Wolverton M. A survey of research in distributed, continual planning. Artificial Intelligence Magazine, 1999,20(4):13-22.
    [2] Frigioni D, Marchetti-Spaccamela A, Nanni U. Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms, 2000,34(2):251-281.
    [3] Stuart Russell, Peter Norvig. Artificial Intelligence: A modern Approach. Pearson Education, Inc., 2002.
    [4] Korf RE. Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 1985,27(1):97-109.
    [5] Koenig S, Furcy D, Bauer C. Heuristic search-based replanning. In: Ghallab M, Herbzberg J, Traverso P, eds. Proc. of the 6th Int’l Conf. on Artificial Intelligence Planning and Scheduling. AIPS 2002. Menlo Park: AAAI Press, 2002. 294-301.
    [6] Ausiello G, Italiano G, Marchetti-Spaccamela A, Nanni U. Incremental algorithms for minimal length paths. Journal of Algorithms, 1991,12(4):615-638.
    [7] Feuerstein E, Marchetti-Spaccamela A. Dynamic algorithms for shortest paths in planar graphs. Theoretical Computer Science, 1993,116(2):359-371.
    [8] Frigioni D, Marchetti-Spaccamela A, Nanni U. Fully dynamic output bounded single source shortest path problem. In: Proc. of the 7th Annual ACM-SIAM Symp. on Discrete Algorithms. 1996. 212-221.
    [9] Rohnert H. A dynamization of the all pairs least cost path problem. In: Mehlhorn K, ed, Proc. of the Symp. on Theoretical Aspects of Computer Science. New York: Springer-Verlag, 1985. 279-286.
    [10] Edelkamp S. Updating shortest paths. In: Prade H, ed. Proc. of the European Conf. on Artificial Intelligence. 1998. 655-659.
    [11] Koenig S, Likhachev M, Furcy D. Lifelong Planning A*. Artificial Intelligence Journal, 2004,155(1-2):93-146,.
    [12] Frigioni D, Marchetti-Spaccamela A, Nanni U. Fully dynamic algorithms for maintaining shortest path trees. Journal of Algorithms. 2000,34(2):251-281.
    [13] Koenig S, Likhachev M, Liu Y, Furcy D. Incremental heuristic search in artificial intelligence. Artificial Intelligence Magazine, Summer, 2004,25(2):99-112.
    [14] Koenig S, Likhachev M. Improved fast replanning for robot navigation in unknown terrain. In: Proc. of the 2002 IEEE Int’l Conf. on Robotics and Automation. ICRA-2002. 2002. 968-975.
    [15] Ayorkor Mills-Tettey G, Anthony Stentz, Bernardine Dias M. DD* Lite: Efficient incremental search with state dominance. Technical Report, CMU-RI-TR-07-12, Robotics Institute, Carnegie Mellon University, 2007.
    [16] Ramalingam G, Reps T. An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms, 1996,21:267-305.
    [17] Stentz A. The focused D* algorithm for real-time replanning. In: Proc. of the Int’l Joint Conf. on Artificial Intelligence. IJCAI. San Fransisco: Morgan Kanfmann Publishers, 1995. 1652-1659.
    [18] Bryant RE. Symbolic manipulation of Boolean functions using a graphical representation. In: Ofek H, O’Neill LA, eds. Proc. of the 22nd ACM/IEEE Design Automation Conf. DAC. New York: ACM, 1985. 688-694.
    [19] Clarke EM, Jr. Grumberg O, Peled DA. Model Checking. Cambridge: The MIT Press, 1999.
    [20] Edelkamp S, Reffel F. OBDDs in heuristic search. In: Herzog O, Gunter A, eds. Proc. of the 22nd Annual German Conf. on Advances in Artificial Intelligence (KI-98). LNCS 1504, New York: Springer-Verlag, 1998. 81-92.
    [21] Jensen RM, Bryant RE, Manuela M. Veloso. SetA*: An efficient BDD-based heuristic search algorithm. In: Proc. of the 18th National Conf. on Artificial Intelligence and 14th Conf. on Innovative Applications of Artificial Intelligence. AAAI-2002. Menlo Park: AAAI Press, 2002. 668-673.
    [22] Jensen RM, Veloso MM, Bryant RE. State-Set branching: Leveraging BDDs for heuristic search. Artificial Intelligence, 2008,172: 103-139.
    [23] Yue WY, Xu YY, Kaile Su. BDDRPA*: An efficient BDD-based incremental heuristic search algorithm for replanning. In: Sattar A, Kang BH, eds. Proc. of the AI 2006: Advances in Artificial Intelligence, the 19th Australian Joint Conf. on Artificial Intelligence. New York: Springer-Verlag, 2006. 627-636.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

徐艳艳,岳伟亚.基于BDD的增量启发式搜索.软件学报,2009,20(9):2352-2365

Copy
Share
Article Metrics
  • Abstract:5171
  • PDF: 7283
  • HTML: 0
  • Cited by: 0
History
  • Received:July 19,2008
  • Revised:January 15,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2032367Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063