R4-[LogoSpace] - Research during Phase 2 (2007-2010)

Agents in Spatio-Temporal Settings

We consider the problem of agents planning in spatio-temporal settings. To this end we analyze an ATL-based approach [1] for spatial planning through model checking, and an extension to ATEL [2] for representing and planning with spatial beliefs. To evaluate the ATL-based approach we implemented a prototype that is able to produce action plans as a byproduct of a variant of the model checking algorithm. The implemented prototype has some interesting features:

  • it has an interface to embed external programs (interpreted Haskell programs, constraint solvers, etc.) to compute data types and values of expressions that occur as pre-condition in action axioms,
  • it uses decomposition techniques to restrict the search for goal states in a transition graph to relevant subgraphs, and
  • the specification language of multi-agent systems that was developed along with the implementation is already close to specification languages usually considered in the CASL-context, that is, it has structuring elements that allow to reuse and combine given agent specifications.

 

An extension of this prototype combines plan generation with an agent's beliefs about her/his environment. For this we consider a variant of the logic ATEL where the knowledge bases of agents are constructed from answer sets of logic programs, an approach which allows for some kind of default reasoning in multi-agent systems.

Right of Way Golog Demonstrator As an alternative approach to the ATL-based one, we consider agent modeling in the framework of the Situation Calculus. More precisely, we investigate how the Golog programming language (used to describe the behavior of agents) can be enhanced by using qualitative spatial reasoning methods as external procedures. The underlying idea is quite close to the approach of the SailAway demonstrator [3,4,5]. As an application scenario we considered here the task to find conflict-free and rule-compliant action plans for cars meeting at a street intersection. We enhanced the Golog variant IndiGolog with external reasoning done by GQR and empirically analyzed the benefit of the external reasoning procedures [6]. We will apply the same integration of external qualitative reasoning to other Golog variants such as MIndiGolog [7] which will allow us to build a multi-agent reasoning framework.

[1] Wojciech Jamroga. Strategic Planning through Model Checking of ATL Formulae, ICAISC, 2004.
[2] Wiebe van der Hoek, Michael Wooldridge. Cooperation, Knowledge, and Time: Alternating-time Temporal Epistemic Logic and its Applications, Studia Logica, 2003.
[3] Diedrich Wolter, Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Bernhard Nebel, Stefan Wölfl. Qualitative Spatial Reasoning for Rule Compliant Agent Navigation, Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), 2007.
[4] Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Diedrich Wolter, Berhard Nebel, Stefan Wölfl. SailAway: Formalizing navigation rules, Proceedings of the Artificial and Ambient Intelligence Symposium on Spatial Reasoning and Communication (AISB 2007), 2007. pdf
[5] Diedrich Wolter, Frank Dylla, Stefan Wölfl, Jan Oliver Wallgrün, Lutz Frommberger, Bernhard Nebel, Christian Freksa. SailAway: Spatial Cognition in Sea Navigation, Künstliche Intelligenz, 2008. 
[6] Florian Pommerening, Stefan Wölfl, Matthias Westphal. Right-of-Way Rules as Use Case for Integrating GOLOG and Qualitative Reasoning, Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), 2009. pdf
[7] 

Ryan F. Kelly, Adrian R. Pearce. Towards High-Level Programming for Distributed Problem Solving, IAT '06: Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, 2006.

Spatial Planning with Qualitative Constraints

Gripper demonstratorWe investigate how transition systems build on temporalized qualitative spatial calculi can be used as spatio-temporal constraints to ease geometric robot motion planning. To this end we work closely with R7-[PlanSpace] and build on their manipulator problem as a use case, where the required (numerical) configurations of a manipulator arm have to be planned, in order to grasp an object. Our approach is to heuristically search a path through a transition system that represents the position of the manipulator by qualitative relations to other objects in the scene. The transition system is represented as a set of states (qualitative constraint networks) where possible successors states have to satisfy the spatio-temporal constraints introduced by the qualitative neighbourhood graph (cf. [1]). The result of this state-space search is a qualitative description of a possible trajectory given by the qualitative constraints in the path through the transition system. Using quantitative information about the scene we currently transform this description into bounding boxes marking the possible trajectory, which in turn is used by a geometric planning system developed by R7-[PlanSpace] to guide the geometric planning process.

Future work includes a tighter integration of the qualitative and geometric planning process, as well as an investigation into qualitative transition systems for multiple non-static objects.

[1] 

Zhan Cui, Anthony G. Cohn, David A. Randell. Qualitative Simulation Based on a Logical Formalism of Space and Time, Proceedings of the 10th National Conference on Artificial Intelligence (AAAI'92), 1992.

Combinations of Qualitative Constraint Calculi

We have been working on the development of general methods for combining qualitative spatial constraint calculi. These methods allow for using existing calculi to generate new formalisms so that one can describe, and reason about, multiple aspects of a domain within one formalism. Vice versa, many of the existing calculi discussed in the QSTR literature can be represented as combinations of other, simpler and more compact formalisms.

The typical example of a combination of spatial qualitative calculi is the combination of the region connection calculus RCC-8 and the point algebra, first discussed by Gerevini and Renz [1], which results in a formalism in which one can express, and reason about, topological and size information about spatially extended objects. They propose to use a biconstraint approach, that, however, builds on a new kind of representation formalism, which also requires a new algorithm for reasoning. An alternative to this approach is to generate a new qualitative calculus in the usual sense, by exploiting the definition of semantic interdependencies between the component calculi as well as further rules that allow for refining the compositional table that results from an algebraic product construction of the component calculi (e.g. [2]).

In [3] we present a comparison of both approaches: While at first glance the product approach seems worse from a computational point of view, it is in general considerably more expressive. We provided an empirical case study, in which the reasoning performance of the suggested methods was compared on randomly generated test instances. Our results indicate that the construction of a new calculus is not necessarily harder to handle in practice, since it allows for more specific input data and more fine-grained information propagation during reasoning. Similar results from a more general perspective, along with a theoretical analysis of combinations and their tractable fragments have been presented at IJCAI 2009 [4].

[1] Alfonso Gerevini, Jochen Renz. Combining topological and size information for spatial reasoning, Artif. Intell., 2002.
[2] Marco Ragni, Stefan Wölfl. Reasoning about topological and positional information in dynamic settings, Proceedings of the Twenty-First International FLAIRS Conference (2008), 2008. pdf
[3] Matthias Westphal, Stefan Wölfl. Bipath Consistency Revisited, Proceedings of the ECAI'08 Workshop on Spatial and Temporal Reasoning, 2008. pdf
[4] 

Stefan Wölfl, Matthias Westphal. On combinations of binary qualitative constraint calculi, Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009), 2009. pdf

Representation of Spatio-Temporal Beliefs

To develop a cognitively adequate representation formalism of spatial beliefs, we conducted further psychological case studies, in which we analyzed how humans process complex spatial relations as well as negations of spatial expressions. We were able to identify how humans construct preferred mental models in both cases.

It turned out that human reasoning with multiple models constructed out of negated premises is even much more difficult than with positive indeterminate premises [1,2]. Another important factor for understanding human spatial reasoning is to understand how it is possible to construct more complex relations from primitive ones. A central result of this work has been an analysis of the model variation phase with complex relations, in particular, when constraints are violated during this reasoning process. The results of these studies have been integrated in the SRM (Spatial Reasoning in Models) platform, which has previously been developed in R2-[BackSpace].

In another investigation we have analyzed of how the human reasoning process and especially the model variation phase can be described by using a mathematically inspired consequence relation and neighborhood graph [3].

Finally, [4] presents an overall analysis of human difficulties in spatial reasoning, which resulted in a new concept of cognitive complexity. The results presented there can be considered essential to define a formal, but cognitively adequate framework of spatial beliefs.

[1] Marco Ragni, Thomas Fangmeier, Stefan Schleipen. What about negation in spatial reasoning?, Proceedings of the 29th Annual Cognitive Science Conference (CogSci 2007), 2007.
[2] Stefan Schleipen, Marco Ragni, Thomas Fangmeier. Negation in Spatial Reasoning: A Computational Approach, Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), 2007.
[3] Marco Ragni. A Logic for Human Spatial Reasoning, Proceedings of the 30th Annual Cognitive Science Conference (CogSci 08), 2008.
[4] 

Marco Ragni. Räumliche Repräsentation, Komplexität und Deduktion: Eine kognitive Komplexitätstheorie, 2008.