View in EDS

Efficient symbolic search for cost-optimal planning.

Saved in:
Bibliographic Details
Title: Efficient symbolic search for cost-optimal planning.
Authors: Torralba, Álvaro1 torralba@cs.saarland-uni.de, Alcázar, Vidal2 vidal.alcazar.saiz@gmail.com, Kissmann, Peter1 peter.kissmann@googlemail.com, Edelkamp, Stefan3 edelkamp@tzi.de
Source: Artificial Intelligence. Jan2017, Vol. 242, p52-79. 28p.
Subjects: Algorithms -- Social aspects, Regression analysis, Orthogonal functions, Heuristic algorithms, Computational complexity
Abstract: In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A ⁎ search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains. [ABSTRACT FROM AUTHOR]
Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 119463285
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Efficient symbolic search for cost-optimal planning.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Torralba%2C+Álvaro%22">Torralba, Álvaro</searchLink><relatesTo>1</relatesTo><i> torralba@cs.saarland-uni.de</i><br /><searchLink fieldCode="AR" term="%22Alcázar%2C+Vidal%22">Alcázar, Vidal</searchLink><relatesTo>2</relatesTo><i> vidal.alcazar.saiz@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Kissmann%2C+Peter%22">Kissmann, Peter</searchLink><relatesTo>1</relatesTo><i> peter.kissmann@googlemail.com</i><br /><searchLink fieldCode="AR" term="%22Edelkamp%2C+Stefan%22">Edelkamp, Stefan</searchLink><relatesTo>3</relatesTo><i> edelkamp@tzi.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink>. Jan2017, Vol. 242, p52-79. 28p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms+--+Social+aspects%22">Algorithms -- Social aspects</searchLink><br /><searchLink fieldCode="DE" term="%22Regression+analysis%22">Regression analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Orthogonal+functions%22">Orthogonal functions</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic+algorithms%22">Heuristic algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A ⁎ search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=119463285
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.artint.2016.10.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 28
        StartPage: 52
    Subjects:
      – SubjectFull: Algorithms -- Social aspects
        Type: general
      – SubjectFull: Regression analysis
        Type: general
      – SubjectFull: Orthogonal functions
        Type: general
      – SubjectFull: Heuristic algorithms
        Type: general
      – SubjectFull: Computational complexity
        Type: general
    Titles:
      – TitleFull: Efficient symbolic search for cost-optimal planning.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Torralba, Álvaro
      – PersonEntity:
          Name:
            NameFull: Alcázar, Vidal
      – PersonEntity:
          Name:
            NameFull: Kissmann, Peter
      – PersonEntity:
          Name:
            NameFull: Edelkamp, Stefan
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 00043702
          Numbering:
            – Type: volume
              Value: 242
          Titles:
            – TitleFull: Artificial Intelligence
              Type: main
ResultId 1