The Experts below are selected from a list of 44706 Experts worldwide ranked by ideXlab platform
Jörg Hoffmann - One of the best experts on this subject based on the ideXlab platform.
-
strong stubborn set pruning for star topology decoupled State Space Search
Journal of Artificial Intelligence Research, 2019Co-Authors: Daniel Gnad, Jörg Hoffmann, Martin WehrleAbstract:Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State Space Search is a basic method for conducting such an ana...
-
Star-topology decoupled State Space Search
Artificial Intelligence, 2018Co-Authors: Daniel Gnad, Jörg HoffmannAbstract:Abstract State Space Search is a basic method for analyzing reachability in discrete transition systems. To tackle large compactly described transition systems – the State Space explosion – a wealth of techniques (e.g., partial-order reduction) have been developed that reduce the Search Space without affecting the existence of (optimal) solution paths. Focusing on classical AI planning, where the compact description is in terms of a vector of State variables, an initial State, a goal condition, and a set of actions, we add another technique, that we baptize star-topology decoupling, into this arsenal. A star topology partitions the State variables into components so that a single center component directly interacts with several leaf components, but the leaves interact only via the center. Many applications explicitly come with such structure; any classical planning task can be viewed in this way by selecting the center as a subset of State variables separating connected leaf components. Our key observation is that, given such a star topology, the leaves are conditionally independent given the center, in the sense that, given a fixed path of transitions by the center, the possible center-compliant paths are independent across the leaves. Our decoupled Search hence branches over center transitions only, and maintains the center-compliant paths for each leaf separately. As we show, this method has exponential separations to all previous Search reduction techniques, i.e., examples where it results in exponentially less effort. One can, in principle, prune duplicates in a way so that the decoupled State Space can never be larger than the original one. Standard Search algorithms remain applicable using simple transformations. Our experiments exhibit large improvements on standard AI planning benchmarks with a pronounced star topology. 1
-
State Space Search nogood learning online refinement of critical path dead end detectors in planning
Artificial Intelligence, 2017Co-Authors: Marcel Steinmetz, Jörg HoffmannAbstract:Abstract Conflict-directed learning is ubiquitous in constraint satisfaction problems like SAT, but has been elusive for State Space Search on reachability problems like classical planning. Almost all existing approaches learn nogoods relative to a fixed solution-length bound, in which case planning/reachability reduces to a constraint satisfaction problem. Here we introduce an approach to learning more powerful nogoods, that are sound regardless of solution length, i.e., that identify dead-end States for which no solution exists. The key technique we build on are critical-path heuristics h C , relative to a set C of conjunctions. These recognize a dead-end State s, returning h C ( s ) = ∞ , if s has no solution even when allowing to break up conjunctive subgoals into the elements of C. Our key idea is to learn C during Search. Whenever forward Search has identified an unrecognized dead-end s, where h C ( s ) ∞ , we analyze the situation at s, and add new conjunctions into C in a way guaranteeing to obtain h C ( s ) = ∞ . Thus we learn to recognize s, as well as similar dead-ends Search may encounter in the future. We furthermore learn clauses ϕ where s ′ ⊭ ϕ implies h C ( s ′ ) = ∞ , to avoid the overhead of computing h C on every Search State. Arranging these techniques in a depth-first Search, we obtain an algorithm approaching the elegance of nogood learning in constraint satisfaction, learning to refute Search subtrees. We run comprehensive experiments on solvable and unsolvable planning benchmarks. In cases where forward Search can identify dead-ends, and where h C dead-end detection is effective, our techniques reduce the depth-first Search Space size by several orders of magnitude, and often result in State-of-the-art performance.
-
towards clause learning State Space Search learning to recognize dead ends
National Conference on Artificial Intelligence, 2016Co-Authors: Marcel Steinmetz, Jörg HoffmannAbstract:We introduce a State Space Search method that identifies deadend States, analyzes the reasons for failure, and learns to avoid similar mistakes in the future. Our work is placed in classical planning. The key technique are critical-path heuristics hC, relative to a set C of conjunctions. These recognize a dead-end State s, returning hC (s) = ∞, if s has no solution even when allowing to break up conjunctive subgoals into the elements of C. Our key idea is to learn C during Search. Starting from a simple initial C, we augment Search to identify unrecognized dead-ends s, where hC (s) < ∞. We design methods analyzing the situation at such s, adding new conjunctions into C to obtain hC (s) = ∞, thus learning to recognize s as well as similar dead-ends Search may encounter in the future. We furthermore learn clauses ϕ where s′ ∣∦ ϕ implies hC (s′) = ∞, to avoid the prohibitive overhead of computing hC on every Search State. Arranging these techniques in a depth-first Search, we obtain an algorithm approaching the elegance of clause learning in SAT, learning to refute Search subtrees. Our experiments show that this can be quite powerful. On problems where dead-ends abound, the learning reliably reduces the Search Space by several orders of magnitude.
-
beating lm cut with h max sometimes fork decoupled State Space Search
International Conference on Automated Planning and Scheduling, 2015Co-Authors: Daniel Gnad, Jörg HoffmannAbstract:Factored planning decouples planning tasks into subsets (factors) of State variables. The traditional focus is on handling complex cross-factor interactions. Departing from this, we introduce a form of target-profile factoring, forcing the cross-factor interactions to take the form of a fork, with several leaf factors and one potentially very large root factor. We show that forward State Space Search gracefully extends to such structure, by augmenting regular Search on the root factor with maintenance of the cheapest compliant paths within each leaf factor. We analyze how to guarantee optimality. Connecting to standard heuristics, the performance improvements relative to A* are substantial, and sometimes dramatic: In four IPC benchmark domains, fork-decoupled State Space Search outperforms standard State Space Search even when using hmax in the former vs. LM-cut in the latter.
Daniel Gnad - One of the best experts on this subject based on the ideXlab platform.
-
strong stubborn set pruning for star topology decoupled State Space Search
Journal of Artificial Intelligence Research, 2019Co-Authors: Daniel Gnad, Jörg Hoffmann, Martin WehrleAbstract:Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State Space Search is a basic method for conducting such an ana...
-
Star-topology decoupled State Space Search
Artificial Intelligence, 2018Co-Authors: Daniel Gnad, Jörg HoffmannAbstract:Abstract State Space Search is a basic method for analyzing reachability in discrete transition systems. To tackle large compactly described transition systems – the State Space explosion – a wealth of techniques (e.g., partial-order reduction) have been developed that reduce the Search Space without affecting the existence of (optimal) solution paths. Focusing on classical AI planning, where the compact description is in terms of a vector of State variables, an initial State, a goal condition, and a set of actions, we add another technique, that we baptize star-topology decoupling, into this arsenal. A star topology partitions the State variables into components so that a single center component directly interacts with several leaf components, but the leaves interact only via the center. Many applications explicitly come with such structure; any classical planning task can be viewed in this way by selecting the center as a subset of State variables separating connected leaf components. Our key observation is that, given such a star topology, the leaves are conditionally independent given the center, in the sense that, given a fixed path of transitions by the center, the possible center-compliant paths are independent across the leaves. Our decoupled Search hence branches over center transitions only, and maintains the center-compliant paths for each leaf separately. As we show, this method has exponential separations to all previous Search reduction techniques, i.e., examples where it results in exponentially less effort. One can, in principle, prune duplicates in a way so that the decoupled State Space can never be larger than the original one. Standard Search algorithms remain applicable using simple transformations. Our experiments exhibit large improvements on standard AI planning benchmarks with a pronounced star topology. 1
-
beating lm cut with h max sometimes fork decoupled State Space Search
International Conference on Automated Planning and Scheduling, 2015Co-Authors: Daniel Gnad, Jörg HoffmannAbstract:Factored planning decouples planning tasks into subsets (factors) of State variables. The traditional focus is on handling complex cross-factor interactions. Departing from this, we introduce a form of target-profile factoring, forcing the cross-factor interactions to take the form of a fork, with several leaf factors and one potentially very large root factor. We show that forward State Space Search gracefully extends to such structure, by augmenting regular Search on the root factor with maintenance of the cheapest compliant paths within each leaf factor. We analyze how to guarantee optimality. Connecting to standard heuristics, the performance improvements relative to A* are substantial, and sometimes dramatic: In four IPC benchmark domains, fork-decoupled State Space Search outperforms standard State Space Search even when using hmax in the former vs. LM-cut in the latter.
-
from fork decoupling to star topology decoupling
Annual Symposium on Combinatorial Search, 2015Co-Authors: Daniel Gnad, Joerg Hoffmann, Carmel DomshlakAbstract:Fork decoupling is a recent approach to exploiting problem structure in State Space Search. The problem is assumed to take the form of a fork, where a single (large) center component provides preconditions for several (small) leaf components. The leaves are then conditionally independent in the sense that, given a fixed center path C , the compliant leaf moves ‐ those leaf moves enabled by the preconditions supplied along C ‐ can be scheduled independently for each leaf. Fork-decoupled State Space Search exploits this through conducting a regular Search over center paths, augmented with maintenance of the compliant paths for each leaf individually. We herein show that the same ideas apply to much more general star-topology structures, where leaves may supply preconditions for the center, and actions may affect several leaves simultaneously as long as they also affect the center. Our empirical evaluation in planning, super-imposing star topologies by automatically grouping the State variables into suitable components, shows the merits of the approach.
Sriram K Rajamani - One of the best experts on this subject based on the ideXlab platform.
-
partial order reduction in symbolic State Space exploration
Formal Methods, 2001Co-Authors: Rajeev Alur, Robert K Brayton, Thomas A Henzinger, Shaz Qadeer, Sriram K RajamaniAbstract:State-Space explosion is a fundamental obstacle in the formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reduction and symbolic State-Space Search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable States. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable States as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first Search for the analysis of asynchronous network protocols, and symbolic breadth-first Search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.
-
partial order reduction in symbolic State Space exploration
Computer Aided Verification, 1997Co-Authors: Rajeev Alur, Robert K Brayton, Thomas A Henzinger, Shaz Qadeer, Sriram K RajamaniAbstract:State Space explosion is a fundamental obstacle in formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reductions and symbolic State Space Search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable States. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable States as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first Search for the analysis of asynchronous network protocols, and symbolic breadth-first Search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.
Rajeev Alur - One of the best experts on this subject based on the ideXlab platform.
-
partial order reduction in symbolic State Space exploration
Formal Methods, 2001Co-Authors: Rajeev Alur, Robert K Brayton, Thomas A Henzinger, Shaz Qadeer, Sriram K RajamaniAbstract:State-Space explosion is a fundamental obstacle in the formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reduction and symbolic State-Space Search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable States. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable States as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first Search for the analysis of asynchronous network protocols, and symbolic breadth-first Search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.
-
partial order reduction in symbolic State Space exploration
Computer Aided Verification, 1997Co-Authors: Rajeev Alur, Robert K Brayton, Thomas A Henzinger, Shaz Qadeer, Sriram K RajamaniAbstract:State Space explosion is a fundamental obstacle in formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reductions and symbolic State Space Search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable States. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable States as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first Search for the analysis of asynchronous network protocols, and symbolic breadth-first Search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.
Eric A Hansen - One of the best experts on this subject based on the ideXlab platform.
-
dynamic State Space partitioning in external memory graph Search
International Conference on Automated Planning and Scheduling, 2011Co-Authors: Rong Zhou, Eric A HansenAbstract:The scalability of optimal sequential planning can be improved by using external-memory graph Search. State-of-the-art external-memory graph Search algorithms rely on a State-Space projection function, or hash function, that partitions the stored nodes of the State-Space Search graph into groups of nodes that are stored as separate files on disk. Search performance depends on properties of the partition; whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the State-Space graph are partitioned, and how well the partition captures local structure in the graph. Previous work relies on a static partition of the State Space, but it can be difficult for a static partition to simultaneously satisfy all of these criteria. We introduce a method for dynamic partitioning and show that it leads to improved Search performance in solving STRIPS planning problems.
-
dynamic State Space partitioning in external memory graph Search
Dagstuhl Seminar Proceedings, 2010Co-Authors: Rong Zhou, Eric A HansenAbstract:State-of-the-art external-memory graph Search algorithms rely on a hash function, or equivalently, a State-Space projection function, that partitions the stored nodes of the State-Space Search graph into groups of nodes that are stored as separate files on disk. The scalability and efficiency of the Search depends on properties of the partition: whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the State-Space graph are partitioned, and how well the partitioning of the State Space captures local structure in the graph. All previous work relies on a static partitioning of the State Space. In this paper, we introduce a method for dynamic partitioning of the State-Space Search graph and show that it leads to substantial improvement of Search performance.