Star-Topology Decoupling – A new Paradigm in State Space Search
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.
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. This method has exponential separations to all previous search reduction techniques, i.e., examples where it results in exponentially less effort. Standard search algorithms remain applicable using simple transformations. Our experiments exhibit large improvements on standard AI planning benchmarks with a pronounced star topology.
March 21, 2019 (Thursday)
Room 205, Building E, Karlovo nám. 13
Daniel Gnad is a Ph.D. student at the Foundations of Artificial Intelligence group at Saarland University. His research is in the field of classical AI planning, mainly focusing on the newly developed concept of star-topology decoupled search. Besides, he has also worked on partial delete-relaxation heuristics and partial grounding techniques.
Álvaro Torralba is a postdoctoral researcher in the FAI group of Saarland University. He received his Ph.D. from Universidad Carlos III de Madrid in 2015. His main research interests are on heuristic search and automated planning.