82 AI MAGAZINE
abstractions that allow a reduction to classical model
checking; and on the other, by devising new model
checking–inspired verification techniques specifically
tailored for the situation calculus and GOLOG. Decid-
ability results were obtained for a large class of of action
theories, where restrictions were imposed on the (con-
ditional) effects of actions. Moreover, the verification
of GOLOG programs with sensing actions, where the
agent’s knowledge is formulated in an epistemic
description logic, was also shown to be decidable.
We are currently advancing the applicability of
such verification methods towards more realistic scenarios, with a special focus on robotics applications.
In particular, we are going beyond mere decidability
to study the feasibility of verification, incorporate
notions of continuous change as well as probabilistic
uncertainty, and consider the case where models of
the dynamics of the environment exist as well.
The principal investigators are Wolfram Burgard
and Gerhard Lakemeyer.
Advanced Solving Technology for
Dynamic and Reactive Applications
Online applications are applications for which rele-
vant additional information may become available at
any time during the solving process. This project aims
to provide hybrid reasoning methods suitable for
such applications. We investigate argumentative rea-
soning methods and reactive multicontext systems
(that is, systems that integrate different reasoners in
a systematic way). A main focus, however, is on
answer set programming (ASP).
Although ASP is being used more and more to tackle industrial problems, certain aspects are more naturally modeled using variables over finite domains
rather than in standard ASP. Consider a planning
problem that involves scheduling different machines,
each of them producing goods while also consuming
energy and material. Resources like runtime, power,
fuel, and storage are difficult to handle with propositional approaches. Therefore, in ASP, a dedicated
treatment of numeric variables and constraints — as
available in constraint processing — is needed. We
extended ASP with constraints over integers, while
preserving its declarative nature and excellent performance.
This strategy resulted in the hybrid ASP solver
clingcon, which enhances the learning techniques of
an ASP solver with the inferences induced by the
underlying constraint satisfaction problem in a lazy
way. In other words, the relevant knowledge is made
explicit only when needed. This delay is useful in
reactive solving, for instance, in online planning with
continuous domains and durations.
In collaboration with Fraunhofer IML, Dortmund,
the ASP techniques developed in the project have
been applied to logistics problems. A Cellular Trans-
port System is a goods-to-person order picking system
in which autonomous vehicles provide picking sta-
tions with article bins. We set up a multiagent system
with the vehicles being modeled as ASP agents that
select driving jobs from a horizon. We provide the
agents with knowledge restricted to the scope of their
specific tasks, which plays a critical role for their per-
formance, especially when the planning horizon is
large. The approach is tailored to work in a real-life
environment, and its evaluation shows a considerable
improvement of performance without any physical
adjustment of the system.
Warehouse planning is a strategic task that requires
a tremendous amount of expert knowledge. We developed a software tool that makes use of the strengths of
ASP, especially complete declarativeness, understandability, and solving efficiency, to facilitate warehouse
planners. In particular, the tool supports process planning, technology dimensioning, and selection and
layout generation, as well as the assessment of alternatives. The inclusion of expert knowledge enables
even inexperienced designers to create a number of
feasible and valuable planning alternatives.
The principal investigators are Gerhard Brewka,
Gabriele Kern-Isberner, and Torsten Schaub.
Probabilistic Description Logics Based
on the Aggregating Semantics and
the Principle of Maximum Entropy
Description Logics (DLs) are a well-investigated fam-
ily of logic-based knowledge representation languages
that are tailored towards representing terminological
knowledge. Probabilistic extensions of DLs are moti-
vated by the fact that, in many application domains,
knowledge is not always certain. In such extensions,
there is a need for treating knowledge about specific
individuals differently from general terminological
knowledge. In a nutshell, probabilistic terminological
knowledge has a statistical flavor, whereas probabilis-
tic knowledge about individuals is rather subjective.
Previous work in this area has not addressed this dual
need in a satisfactory way.
The main idea underlying this project is to adapt
and extend the recently developed aggregating
semantics for probabilistic knowledge from a restricted first-order case to DLs. This semantics seems suitable for the project goals, as it combines subjective
probabilities with population-based statements on
the basis of a possible-world semantics. It thus provides a common semantic framework for both subjective and statistical probabilities.
As a second main feature, we apply the principle of
maximum entropy on top of aggregating semantics.
This approach overcomes the pitfall of obtaining
large and uninformative intervals for inferred probabilities, which is a common feature of many
approaches that reason with respect to sets of probability distributions.