At these practice talks, there will be pizza served.
1. Title: A Correctness Result for Reasoning about OneDimensional Planning Problems
Authors: Yuxiao Hu and Hector J. Levesque
Abstract: A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is nontrivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call onedimensional (1d), and prove a correctness result that 1d problems can be verified by finite means.
We show that this theoretical result leads to an algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.
2. Title: Generalized Planning: Synthesizing Plans that Work for Multiple Environments
Authors: Yuxiao Hu and Giuseppe De Giacomo
Abstract: We give a formal definition of generalized planning that is independent of any representation formalism. We assume that our generalized plans must work on a set of deterministic environments, which are essentially unrelated to each other. We prove that generalized planning for a finite set of environments is always decidable and EXPSPACEcomplete. Our proof is constructive and gives us a sound, complete and complexitywise optimal technique. We also consider infinite sets of environments, and show that generalized planning for the infinite “onedimensional problems,” known in the literature to be recursively enumerable when restricted to finitestate plans, is EXPSPACEdecidable without sequence functions, and solvable by generalized planning for finite sets.
3. Title: Multidimensional Mereotopology with Betweenness
Authors: Torsten Hahmann and Michael Gruninger
Abstract: This work extends the multidimensional mereotopology that we developed previously with some notion of order/betweenness amongst entities. Such a relation is essential in order to preserve characteristic qualitative properties of city or building maps that are beyond standard topological and mereological relations. We show that the resulting multidimensional mereotoplogy with betweenness is a qualitative abstraction of ordered incidence geometry. First, we show that extensions of the original multidimensional mereotopology are faithfully interpreted by kpartite incidence structures and bipartite incidence geometry.
Together with the betweenness relation we can then reconstruct a theory that is weaker than existing ordered incidence geometries in two aspects: Entities can be (1) arbitrarily curved (not necessarily straight or planar) and (2) are not always continuous.
