Nebel, Bernhard


Transition Constraints: A Study on the Computational Complexity of Qualitative Change

AAAI Conferences

Many formalisms discussed in the literature on qualitative spatial reasoning are designed for expressing static spatial constraints only. However, dynamic situations arise in virtually all applications of these formalisms, which makes it necessary to study variants and extensions involving change. This paper presents a study on the computational complexity of qualitative change. More precisely, we discuss the reasoning task of finding a solution to a temporal sequence of static reasoning problems where this sequence is subject to additional transition constraints. Our focus is primarily on smoothness and continuity constraints: we show how such transitions can be defined as relations and expressed within qualitative constraint formalisms. Our results demonstrate that for point-based constraint formalisms the interesting fragments become NP-completein the presence of continuity constraints, even if the satisfiability problem of its static descriptions is tractable.


Domain Predictive Control Under Uncertain Numerical State Information

AAAI Conferences

In planning, hybrid system states consisting of logical and numerical variables are usually assumed to be completely known. In particular, for numerical state variables full knowledge of their exact values is assumed. However, in real world applications states are results of noisy measurements and imperfect actuators. Therefore, a planned sequence of state transitions might fail to lead a hybrid system to the desired goal. We show how to propagate and reason about uncertain state information directly in the planning process, enabling hybrid systems to find plans that satisfy numerical goals with predefined confidence.


A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions

AAAI Conferences

Car pollution is one of the major causes of green-house emissions, and traffic congestion is rapidly becoming a social plague. Dynamic Ride Sharing (DRS) systems have the potential to mitigate this problem by computing plans for car drivers, e.g. commuters, allowing them to share their rides. Existing efforts in DRS are suffering from the problem that participants are abandoning the system after repeatedly failing to get a shared ride. In this paper we present an incentive compatible DRS solution based on auctions. While existing DRS systems are mainly focusing on fixed assignments that min- imize the totally travelled distance, the presented approach is adaptive to individual preferences of the participants. Furthermore, our system allows to tradeoff the minimization of Vehicle Kilometers Travelled (VKT) with the overall probability of successful ride-shares, which is an important fea- ture when bootstrapping the system. To the best of our knowledge, we are the first to present a DRS solution based on auctions using a sealed-bid second price scheme.



Reports of the AAAI 2009 Spring Symposia

AI Magazine

The titles of the nine symposia were Agents that Learn from Human Teachers, Benchmarking of Qualitative Spatial and Temporal Reasoning Systems, Experimental Design for Real-World Systems, Human Behavior Modeling, Intelligent Event Processing, Intelligent Narrative Technologies II, Learning by Reading and Learning to Read, Social Semantic Web: Where Web 2.0 Meets Web 3.0, and Technosocial Predictive Analytics. The aim of the Benchmarking of Qualitative Spatial and Temporal Reasoning Systems symposium was to initiate the development of a problem repository in the field of qualitative spatial and temporal reasoning and identify a graded set of challenges for future midterm and long-term research. The Intelligent Event Processing symposium discussed the need for more AI-based approaches in event processing and defined a kind of research agenda for the field, coined as intelligent complex event processing (iCEP). The Intelligent Narrative Technologies II AAAI symposium discussed innovations, progress, and novel techniques in the research domain.


Reports of the AAAI 2009 Spring Symposia

AI Magazine

The Association for the Advancement of Artificial Intelligence, in cooperation with Stanford University's Department of Computer Science, was pleased to present the 2009 Spring Symposium Series, held Monday through Wednesday, March 23–25, 2009 at Stanford University. The titles of the nine symposia were Agents that Learn from Human Teachers, Benchmarking of Qualitative Spatial and Temporal Reasoning Systems, Experimental Design for Real-World Systems, Human Behavior Modeling, Intelligent Event Processing, Intelligent Narrative Technologies II, Learning by Reading and Learning to Read, Social Semantic Web: Where Web 2.0 Meets Web 3.0, and Technosocial Predictive Analytics. The goal of the Agents that Learn from Human Teachers was to investigate how we can enable software and robotics agents to learn from real-time interaction with an everyday human partner. The aim of the Benchmarking of Qualitative Spatial and Temporal Reasoning Systems symposium was to initiate the development of a problem repository in the field of qualitative spatial and temporal reasoning and identify a graded set of challenges for future midterm and long-term research. The Experimental Design symposium discussed the challenges of evaluating AI systems. The Human Behavior Modeling symposium explored reasoning methods for understanding various aspects of human behavior, especially in the context of designing intelligent systems that interact with humans. The Intelligent Event Processing symposium discussed the need for more AI-based approaches in event processing and defined a kind of research agenda for the field, coined as intelligent complex event processing (iCEP). The Intelligent Narrative Technologies II AAAI symposium discussed innovations, progress, and novel techniques in the research domain. The Learning by Reading and Learning to Read symposium explored two aspects of making natural language texts semantically accessible to, and processable by, machines. The Social Semantic Web symposium focused on the real-world grand challenges in this area. Finally, the Technosocial Predictive Analytics symposium explored new methods for anticipatory analytical thinking that provide decision advantage through the integration of human and physical models.


Semantic Attachments for Domain-Independent Planning Systems

AAAI Conferences

Solving real-world problems using symbolic planning often requires a simplified formulation of the original problem, since certain subproblems cannot be represented at all or only in a way leading to inefficiency. For example, manipulation planning may appear as a subproblem in a robotic planning context or a packing problem can be part of a logistics task. In this paper we propose an extension of PDDL for specifying semantic attachments. This allows the evaluation of grounded predicates as well as the change of fluents by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into a forward-chaining planner and report on our experience of adding this extension to the planners FF and Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.


A Fixed-Parameter Tractable Algorithm for Spatio-Temporal Calendar Management

AAAI Conferences

Calendar management tools assist users with coordinating their daily life. Different tasks have to be scheduled according to the user preferences. In many cases, tasks are at different locations and travel times have to be considered. Therefore, these kinds of calendar management problems can be regarded as spatio-temporal optimisation problems and are often variants of traveling salesman problems (TSP) or vehicle routing problems. While standard TSPs require a solution to include all tasks, prize-collecting TSPs are more suited for calendar management problems as they require a solution that optimises the total sum of prizes we assigned to tasks at different locations. If we now add time windows that limit when tasks can occur, these prize-collecting TSPs with time windows (TW-TSP) are excellent abstractions of spatio-temporal optimisation problems such as calendar management. Due to the inherent complexity of TW-TSPs, the existing literature considers mainly approximation algorithms or special cases. We present a novel algorithm for TW-TSPs that enables us to find the optimal solution to TW-TSP problems occurring in real-world calendar management applications efficiently. Our algorithm is a fixed-parameter tractable algorithm that depends on the maximal number of tasks that can be revisited from some other task, a parameter which is small in the application scenario we consider.


The CS Freiburg Team: Playing Robotic Soccer Based on an Explicit World Model

AI Magazine

Robotic soccer is an ideal task to demonstrate new techniques and explore new problems. Our intention in building a robotic soccer team and participating in RoboCup-98 was, first, to demonstrate the usefulness of the self-localization methods we have developed. Second, we wanted to show that playing soccer based on an explicit world model is much more effective than other methods. Third, we intended to explore the problem of building and maintaining a global team world model.


The CS Freiburg Team: Playing Robotic Soccer Based on an Explicit World Model

AI Magazine

Robotic soccer is an ideal task to demonstrate new techniques and explore new problems. Moreover, problems and solutions can easily be communicated because soccer is a well-known game. Our intention in building a robotic soccer team and participating in RoboCup-98 was, first, to demonstrate the usefulness of the self-localization methods we have developed. Second, we wanted to show that playing soccer based on an explicit world model is much more effective than other methods. Third, we intended to explore the problem of building and maintaining a global team world model. As has been demonstrated by the performance of our team, we were successful with the first two points. Moreover, robotic soccer gave us the opportunity to study problems in distributed, cooperative sensing.