-
Bernhard Nebel.
The Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.
Artificial Intelligence. 2024.
(Show abstract)
(Hide abstract)
(Preprint; PDF)
(Online; DOI)
While the non-optimizing variant of multi-agent pathfinding on undirected graphs is known to be a polynomial-time problem since almost forty years, a similar result has not been established for directed graphs. In this paper, it will be shown that this problem is NP-complete. For strongly connected directed graphs, however, the problem is polynomial. And both of these results hold even if one allows for synchronous rotations on fully occupied cycles. Interestingly, the results apply also to the so-called motion planning feasibility problem on directed graphs.
-
Moritz Graf, Thorsten Engesser and Bernhard Nebel.
A Symbolic Sequential Equilibria Solver for Game Theory Explorer (Demo Track).
In
Proceedings of the 23rd Int. Joint Conf. on Autonomous Agents and Multiagent Systems
(AAMAS 2024).
2024.
(Show abstract)
(Hide abstract)
We present the first implemented symbolic solver for sequential equilibria in general finite imperfect information games.
-
Moritz Graf, Thorsten Engesser and Bernhard Nebel.
Symbolic Computation of Sequential Equilibria.
In
Proceedings of the 23rd Int. Joint Conf. on Autonomous Agents and Multiagent Systems
(AAMAS 2024).
2024.
(Show abstract)
(Hide abstract)
The sequential equilibrium is a standard solution concept for extensive-form games with imperfect information that includes an explicit representation of the players' beliefs. An assessment consisting of a strategy and a belief is a sequential equilibrium if it satisfies the properties of sequential rationality and consistency.
Our main result is that both properties together can be written as a finite set of polynomial equations and inequalities. The solutions to this system are exactly the sequential equilibria of the game. We construct this system explicitly and describe an implementation that solves it using cylindrical algebraic decomposition. To write consistency as a finite system of equations, we need to compute the extreme directions of a set of polyhedral cones. We propose a modified version of the double description method, optimized for this specific purpose. To the best of our knowledge, our implementation is the first to symbolically solve general finite imperfect information games for sequential equilibria.
-
Stefano Ardizzoni, Irene Saccani, Luca Consolini, Marco Locatelli and Bernhard Nebel.
An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees.
Journal of Artificial Intelligence Research 79. 2024.
(Show abstract)
(Hide abstract)
(Online; DOI)
The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(|P|nc + n2), where n is the number of nodes, P is the set of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n3), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.
-
Moritz Graf, Thorsten Engesser and Bernhard Nebel.
Symbolic Computation of Sequential Equilibria.
Technical Report arXiv:2402.04452,
arxiv cs.GT, 2024.
(Show abstract)
(Hide abstract)
(Online; DOI)
The sequential equilibrium is a standard solution concept for extensive-form games with imperfect information that includes an explicit representation of the players' beliefs. An assessment consisting of a strategy and a belief is a sequential equilibrium if it satisfies the properties of sequential rationality and consistency.
Our main result is that both properties together can be written as a single finite system of polynomial equations and inequalities. The solutions to this system are exactly the sequential equilibria of the game. We construct this system explicitly and describe an implementation that solves it using cylindrical algebraic decomposition. To write consistency as a finite system of equations, we need to compute the extreme directions of a set of polyhedral cones. We propose a modified version of the double description method, optimized for this specific purpose. To the best of our knowledge, our implementation is the first to symbolically solve general finite imperfect information games for sequential equilibria.
-
Stefano Ardizzoni, Irene Saccani, Luca Consolini, Marco Locatelli and Bernhard Nebel.
An algorithm with improved complexity for pebble motion/multi-agent
path finding on trees.
Technical Report arXiv:2307.12770,
arxiv cs.AI, 2023.
(Show abstract)
(Hide abstract)
(Online)
The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT.
We propose a simple and easy to implement procedure, which finds solutions of length O(knc + n^2), where n is the number of nodes, k is the number of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n^3), which is equal to our result in the worst case, but does not capture the dependency on c and k.
-
Vaishak Belle, Thomas Bolander, Andreas Herzig and Bernhard Nebel.
Epistemic planning: Perspectives on the special issue.
Artificial Intelligence 316, p. 103842. 2023.
(Show abstract)
(Hide abstract)
(Online; DOI)
Epistemic planning is the enrichment of automated planning with epistemic notions such as knowledge and belief. In general, single-agent epistemic planning considers the following problem: given an agent's current state of knowledge, and a desirable state of knowledge, how does it get from one to the other? In multi-agent epistemic planning, the current and desirable states of knowledge might also refer to the states of knowledge of other agents, including higher-order knowledge like ensuring that agent A doesn't get to know that agent B knows P. Single-agent epistemic planning is of central importance in settings where agents need to be able to reason about their own lack of knowledge and, e.g., make plans of how to achieve the required knowledge. Multi-agent epistemic planning is essential for coordination and collaboration among multiple agents, where success can only be expected if agents are able to reason about the knowledge, uncertainty and capabilities of other agents. It is a relatively recent area of research involving several sub-areas of artificial intelligence, such as automated planning, decision-theoretic planning, epistemic logic, strategic reasoning and knowledge representation and reasoning. In
order to achieve formalisms and systems for epistemic planning that are both expressive and practically efficient, it is necessary to combine state of the art from several such sub-areas of artificial intelligence that have so far been considered mostly in separation. Application areas of epistemic planning include mobile service robots, explaining planning, game playing, human-robot interaction and social robotics. For this special issue of AIJ, we invited papers on theory, applications, and implemented systems of epistemic planning. In this document, we summarize the accepted papers whilst recapping the essentials of epistemic planning.
-
Bernhard Nebel.
The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True.
In
Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 304-313.
2023.
(Show abstract)
(Hide abstract)
(Online; DOI)
The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. Only recently, it has been established that the problem is NP-hard. Further, it has been proved that it is in NP, provided the short solution hypothesis for strongly connected digraphs holds. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.
-
Pascal Bachor, Rolf-David Bergdoll and Bernhard Nebel.
The Multi-Agent Transportation Problem.
In
Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 11525-11532.
2023.
(Show abstract)
(Hide abstract)
(Online; DOI)
We introduce the multi-agent transportation (MAT) problem,
where agents have to transport containers from their starting
positions to their designated goal positions. Movement takes place
in a common environment where collisions between agents and between
containers must be avoided. In contrast to other frameworks such as
MAPF or MAPD, the agents are allowed to separate from the containers
at any time, which allows for plans in scenarios that might
otherwise be unsolvable and has the potential to reduce the
makespan. We present a complexity analysis establishing
NP-completeness and show how the problem can be reduced to a
sequence of SAT problems when optimizing for makespan. Finally, the
implementation is empirically evaluated relative to input
characteristics, and it is compared to some variants of the MAT
problem and a CBS-based MAPD implementation.
-
Bernhard Nebel.
The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True.
Technical Report arXiv:2210.04590,
arxiv cs.AI, 2022.
(Show abstract)
(Hide abstract)
(Online; PDF)
The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. Only recently, it has been established that the problem is NP-hard. Further, it has been proved that it is in NP, provided the short solution hypothesis for strongly connected digraphs holds. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.
-
Stefan Borgwardt, Jörg Hoffmann, Alisa Kovtunova, Markus Krötzsch, Bernhard Nebel and Marcel Steinmetz.
Expressivity of Planning with Horn Description Logic Ontologies (Extended Abstract).
In
Proceedings of the 35th International Workshop on Description Logics (DL 2022).
2022.
(Online; PDF)
-
Stefan Borgwardt, Jörg Hoffmann, Alisa Kovtunova, Markus Krötzsch, Bernhard Nebel and Marcel Steinmetz.
Expressivity of Planning with Horn Description Logic Ontologies (Technical Report).
Technical Report arXiv:2203.09361,
arxiv cs.AI, 2022.
(Show abstract)
(Hide abstract)
(Online; DOI)
State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-world state constraints formalized by planning over a description logic (DL) ontology. Previously, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies, and is feasible on new benchmarks taking advantage of more expressive ontologies.
-
Stefan Borgwardt, Jörg Hoffmann, Alisa Kovtunova, Markus Krötzsch, Bernhard Nebel and Marcel Steinmetz.
Expressivity of Planning with Horn Description Logic Ontologies.
In
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022).
2022.
(Show abstract)
(Hide abstract)
(Online; DOI)
State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-world state constraints formalized by planning over a description logic (DL) ontology. Previously, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies, and is feasible on new benchmarks taking advantage of more expressive ontologies.
-
Bernhard Nebel and Stefan Wölfl.
Wissensrepräsentation und -verarbeitung.
In
Günther Görz, Ute Schmid and Tanya Braun (eds.),
Handbuch der Künstlichen Intelligenz, 6. Auflage, pp. 27-56.
De Gruyter 2020.
(Online; DOI)
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Felicitas Ritter.
Token-based Execution Semantics for Multi-Agent Epistemic Planning.
In
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR-2020), pp. 351-360.
2020.
(Show abstract)
(Hide abstract)
(Online; PDF)
Epistemic planning has been employed as a means to achieve implicit coordination in cooperative multi-agent systems where world knowledge is distributed between the agents, and agents plan and act individually. However, recent work has shown that even if all agents act with respect to plans that they consider optimal from their own subjective perspective, infinite executions can occur. In this paper, we analyze the idea of using a single token that can be passed around between the agents and which is used as a prerequisite for acting. We show that introducing such a token to any planning task will prevent the existence of infinite executions. We furthermore analyze the conditions under which solutions to a planning task are preserved under our tokenization.
-
Lukas Berger, Bernhard Nebel and Marco Ragni.
A Heuristic Agent in Multi-Agent Path Finding Under Destination Uncertainty.
In
KI 2020: Advances in Artificial Intelligence - 43rd German Conference on AI,, pp. 259-266.
2020.
(Show abstract)
(Hide abstract)
(Online; DOI)
Humans are capable of recognizing intentions by solely observing another agent’s actions. Hence, in a cooperative planning task, i.e., where all agents aim for all other agents to reach their respective goals, to some extend communication or a central planning instance are not necessary. In epistemic planning a recent research line investigates multi-agent planning problems (MAPF) with goal uncertainty. In this paper, we propose and analyze a round-based variation of this problem, where each agent moves or waits in each round. We show that simple heuristics from cognition can outperform in some cases an adapted formal approach on computation time and solve some new instances in some cases. Implications are discussed.
-
Felix Lindner, Robert Mattmüller and Bernhard Nebel.
Evaluation of the Moral Permissibility of Action
Plans.
Artificial Intelligence 287. 2020.
(Show abstract)
(Hide abstract)
(PDF)
Research in classical planning so far has been mainly concerned with
generating a satisficing or an optimal plan. However, if such
systems are used to make decisions that are relevant to humans, one
should also consider the ethical consequences generated plans can have.
Traditionally, ethical principles are formulated
in an action-based manner, allowing to judge the execution
of one action. We show how such a judgment can be generalized to
plans. Further, we study the computational complexity of making ethical judgment
about plans.
-
Bernhard Nebel.
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.
In
Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 212-216.
2020.
(Show abstract)
(Hide abstract)
(Online; PDF)
The determination of the computational complexity of multi-agent
pathfinding on directed graphs has been an open problem for
many years. For undirected graphs, solvability can be decided in
polynomial time, as has been shown already in the eighties. Further,
recently it has been shown that a
special case on directed graphs can be decided in polynomial time. In
this paper, we show that the problem is
NP-hard in the general case. In addition, some upper bounds are
proven.
-
David Speck, Robert Mattmüller and Bernhard Nebel.
Symbolic Top-k Planning.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967-9974.
2020.
(Show abstract)
(Hide abstract)
(PDF)
The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task. In practice, such a set of best plans can be preferred to a single best plan generated by ordinary optimal planners, as it allows the user to choose between different alternatives and thus take into account preferences that may be difficult to model. In this paper we show that, in general, the decision problem version of top-k planning is PSPACE-complete, as is the decision problem version of ordinary classical planning. This does not hold for polynomially bounded plans for which the decision problem turns out to be PP-hard, while the ordinary case is NP-hard. We present a novel approach to top-k planning, called SYM-K, which is based on symbolic search, and prove that SYM-K is sound and complete. Our empirical analysis shows that SYM-K exceeds the current state of the art for both small and large k.
-
Bernhard Nebel.
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.
Technical Report arXiv:1911.04871,
arxiv cs.AI, 2019.
(Show abstract)
(Hide abstract)
(Online; PDF)
The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs is solvable in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.
-
Daniel Reifsteck, Thorsten Engesser, Robert Mattmüller and Bernhard Nebel.
Epistemic Multi-agent Planning Using Monte-Carlo Tree Search.
In
KI 2019: Advances in Artificial Intelligence - 42nd German Conference on AI, pp. 277-289.
2019.
(Show abstract)
(Hide abstract)
(Online; DOI)
Coordination in multi-agent systems with partial and non-uniform observability is a practically challenging problem. We use Monte-Carlo tree search as the basis of an implicitly coordinated epistemic planning algorithm which is capable of using the knowledge distributed among the agents to find solutions in problems even with a large branching factor. We use Dynamic Epistemic Logic to represent the knowledge and the actual situation as a state of the Monte-Carlo tree search, and epistemic planning to formalize the goals and actions of a problem. Further, we describe the required modifications of the Monte-Carlo tree search when searching over epistemic states, and make use of the cooperative card game Hanabi to test our planner on larger problems. We find that the approach scales to games with up to eight cards while maintaining high playing strength.
-
Tim Schulte and Bernhard Nebel.
Trial-based Heuristic Tree-search for Distributed Multi-Agent Planning.
In
Proceedings of the Twelfth Annual Symposium on Combinatorial Search (SoCS 2019)
(SoCS 2019).
2019.
(Show abstract)
(Hide abstract)
(PDF)
We present a novel search scheme for privacy-preserving multi-agent
planning, inspired by UCT search. We compare the presented approach to
classical multi-agent forward search and evaluate it based on benchmarks
from the CoDMAP competition.
-
Bernhard Nebel, Thomas Bolander, Thorsten Engesser, Robert Mattmüller and .
Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity (Extended Abstract).
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 6372-6374.
2019.
-
Bernhard Nebel.
Some Thoughts on Forward Induction in Multi-Agent-Path Finding Under
Destination Uncertainty.
In
Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday.
Springer-Verlag, Berlin, Heidelberg, New York 2019.
(Show abstract)
(Hide abstract)
(PDF)
While the notion of implicit coordination helps to design frameworks in which agents can cooperatively act with only minimal communication, it so far lacks exploiting observations made while executing a plan. In this note, we have a look at what can be done in order to overcome this shortcoming, at least in a specialized setting.
-
Thomas Bolander, Thorsten Engesser, Andreas Herzig, Robert Mattmüller and Bernhard Nebel.
The Dynamic Logic of Policies and Contingent Planning.
In
Logics in Artificial Intelligence - 16th European Conference (JELIA-2019), pp. 659-674.
2019.
(Show abstract)
(Hide abstract)
(Online; DOI)
In classical deterministic planning, solutions to planning tasks are simply sequences of actions, but that is not sufficient for contingent plans in non-deterministic environments. Contingent plans are often expressed through policies that map states to actions. An alternative is to specify contingent plans as programs, e.g. in the syntax of Propositional Dynamic Logic (PDL). PDL is a logic for reasoning about programs with sequential composition, test and non-deterministic choice. However, as we show in the paper, none of the existing PDL modalities directly captures the notion of a solution to a planning task under non-determinism. We add a new modality to star-free PDL correctly capturing this notion. We prove the appropriateness of the new modality by showing how to translate back and forth between policies and PDL programs under the new modality. More precisely, we show how a policy solution to a planning task gives rise to a program solution expressed via the new modality, and vice versa. We also provide an axiomatisation of our PDL extension through reduction axioms into standard star-free PDL.
-
Daniel Kuhner, Lukas D.J. Fiederer, Johannes Aldinger, Felix Burget, Martin Völker, Robin T. Schirrmeister, Chau Do, Joschka Boedecker, Bernhard Nebel, Tonio Ball and Wolfram Burgard.
A service assistant combining autonomous robotics, flexible goal formulation, and deep-learning-based brain–computer interfacing.
Robotics and Autonomous Systems 116, pp. 98-113. 2019.
(Show abstract)
(Hide abstract)
(Online; DOI)
As autonomous service robots become more affordable and thus available for the general public, there is a growing need for user-friendly interfaces to control these systems. Control interfaces typically get more complicated with increasing complexity of robotic tasks and environments. Traditional control modalities such as touch, speech or gesture are not necessarily suited for all users. While some users can make the effort to familiarize themselves with a robotic system, users with motor disabilities may not be capable of controlling such systems even though they need robotic assistance most. In this paper, we present a novel framework that allows these users to interact with a robotic service assistant in a closed-loop fashion, using only thoughts. The system is composed of several interacting components: a brain–computer interface (BCI) that uses non-invasive neuronal signal recording and co-adaptive deep learning, high-level task planning based on referring expressions, navigation and manipulation planning as well as environmental perception. We extensively evaluate the BCI in various tasks, determine the performance of the goal formulation user interface and investigate its intuitiveness in a user study. Furthermore, we demonstrate the applicability and robustness of the system in real-world scenarios, considering fetch-and-carry tasks, close human–robot interactions and in presence of unexpected changes. As our results show, the system is capable of adapting to frequent changes in the environment and reliably accomplishes given tasks within a reasonable amount of time. Combined with high-level task planning based on referring expressions and an autonomous robotic system, interesting new perspectives open up for non-invasive BCI-based human–robot interactions.
-
Bernhard Nebel, Thomas Bolander, Thorsten Engesser and Robert Mattmüller.
Implicitly Coordinated Multi-Agent Path Finding under Destination
Uncertainty:
Success Guarantees and Computational Complexity.
Journal of Artificial Intelligence Research 64, pp. 497-527. 2019.
(Show abstract)
(Hide abstract)
(PDF)
In multi-agent path finding (MAPF), it is usually assumed that planning
is performed centrally and that the destinations of the
agents are common knowledge. We will drop both assumptions and analyze
under which conditions it can be guaranteed that the agents reach their
respective destinations using implicitly coordinated
plans without communication. Furthermore, we will analyze what the computational costs
associated with such a coordination regime are. As it turns out,
guarantees can be given assuming that the agents are of a certain
type. However, the implied
computational costs are quite severe. In the distributed setting, we
either have to solve a sequence of NP-complete problems or have to tolerate
exponentially longer executions. In the setting with destination
uncertainty, bounded plan existence becomes PSPACE-complete.
This clearly demonstrates the value of communicating about plans
before execution starts.
-
Felix Lindner, Robert Mattmüller and Bernhard Nebel.
Moral Permissibility of Action Plans.
In
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19).
2019.
(Show abstract)
(Hide abstract)
(PDF)
Research in classical planning so far was mainly concerned with generating a satisficing or an optimal plan. However, if such systems are used to make decisions that are relevant to humans, one should also consider the ethical consequences generated plans can have. We address this challenge by analyzing in how far it is possible to generalize existing approaches of machine ethics to automatic planning systems. Traditionally, ethical principles are formulated in an action-based manner, allowing to judge the execution of one action. We show how such a judgment can be generalized to plans. Further, we study the computational complexity of making ethical judgment about plans.
-
Thomas Bolander, Thorsten Engesser, Robert Mattmüller and Bernhard Nebel.
Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination.
In
Proceedings of the Sixteenth Conference on Principles of Knowledge Representation and Reasoning (KR18), pp. 445-453.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Epistemic planning can be used for decision making in multi-agent situations
with distributed knowledge and capabilities.
In recent work, we proposed a new notion of
strong policies with implicit coordination. With this it is possible to solve
planning tasks with joint goals from a single-agent perspective without the
agents having to negotiate about and commit to a joint policy at plan time. We
study how and under which circumstances the decentralized application of those
policies leads to the desired outcome.
-
Benedict Wright, Robert Mattmüller and Bernhard Nebel.
Compiling Away Soft Trajectory Constraints in Planning.
In
Proceedings of the Sixteenth COnference on Principles of Knowledge Representation and Reasoning (KR18), pp. 474-482.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Soft goals in planning are optional objectives that should be achieved in the terminal state. However, failing to achieve them does not result in the plan becoming invalid. State trajectory constraints are hard requirements towards the state trajectory of the plan. Soft trajectory constraints are a combination of both: soft preferences on how the hard goals are reached, i. e., optional requirements towards the state trajectory of the plan. Such a soft trajectory constraint may require that some fact should be always true, or should be true at some point during the plan. The quality of a plan is then measured by a metric which adds the sum of all action costs and a penalty for each failed soft trajectory constraint. Keyder and Geffner showed that soft goals can be compiled away. We generalize this approach and illustrate a method of compiling soft trajectory constraints into conditional effects and state-dependent action costs using LTL f and deterministic finite automata. We provide two compilation schemes, with and without reward shaping, by rewarding and penalizing different states in the plan. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.
-
Daniel Kuhner, Johannes Aldinger, Felix Burget, Moritz Göbelbecker, Wolfram Burgard and Bernhard Nebel.
Closed-Loop Robot Task Planning Based on Referring Expressions.
In
Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2018), pp. 876-881.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Increasing the accessibility of autonomous robots also for inexperienced users requires user-friendly and high-level control opportunities of robotic systems. While automated planning is able to decompose a complex task into a sequence of steps which reaches an intended goal, it is difficult to formulate such a goal without knowing the internals of the planning system and the exact capabilities of the robot. This becomes even more important in dynamic environments in which manipulable objects are subject to change. In this paper, we present an adaptive control interface which allows users to specify goals based on an internal world model by incrementally building referring expressions to the objects in the world. We consider fetch-and-carry tasks and automatically deduce potential high-level goals from the world model to make them available to the user. Based on its perceptions our system can react to changes in the environment by adapting the goal formulation within the domain-independent planning system.
-
Andreas Hertle and Bernhard Nebel.
Efficient Auction Based Coordination for Distributed Multi-Agent Planning in Temporal Domains Using Resource Abstraction.
In
Proceedings of the 41st German Conference on Artificial Intelligence (KI 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Recent advances in mobile robotics and AI promise to revolutionize industrial production.
As autonomous robots are able to solve more complex tasks, the difficulty of integrating various robot skills and coordinating groups of robots increases dramatically.
Domain independent planning promises a possible solution.
For single robot systems a number of successful demonstrations can be found in scientific literature.
However our experiences at the RoboCup Logistics League in 2017 highlighted a severe lack in plan quality when coordinating multiple robots.
In this work we demonstrate how out of the box temporal planning systems can be employed to increase plan quality for temporal multi-robot tasks.
An abstract plan is generated first and sub-tasks in the plan are auctioned off to robots, which in turn employ planning to solve these tasks and compute bids.
We evaluate our approach on two planning domains and find significant improvements in solution coverage and plan quality.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Michael Thielscher.
Game Description Language and Dynamic Epistemic Logic Compared.
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2018), pp. 1795-1802.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Several different frameworks have been proposed to model and reason about knowledge in dynamic multi-agent settings, among them the logic-programming-based game description language GDL-III, and dynamic epistemic logic (DEL), based on possible-worlds semantics. GDL-III and DEL have complementary strengths and weaknesses in terms of ease of modeling and simplicity of semantics. In this paper, we formally study the expressiveness of GDL-III vs. DEL. We clarify the commonalities and differences between those languages, demonstrate how to bridge the differences where possible, and identify large fragments of GDL-III and DEL that are equivalent in the sense that they can be used to encode games or planning tasks that admit the same legal action sequences. We prove the latter by providing compilations between those fragments of GDL-III and DEL.
-
Benedict Wright, Robert Mattmüller and Bernhard Nebel.
Compiling Away Soft Trajectory Constraints in Planning.
In
Proceedings of the Workshop on Knowledge Engineering for Planning and Scheduling (KEPS18), pp. 38-45.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Soft goals in planning are optional objectives that should be achieved in the terminal state. However, failing to achieve them does not result in the plan becoming invalid. State trajectory constraints are hard requirements towards the state trajectory of the plan. Soft trajectory constraints are a combination of both: soft preferences on how the hard goals are reached, i. e., optional requirements towards the state trajectory of the plan. Such a soft trajectory constraint may require that some fact should be always true, or should be true at some point during the plan. The quality of a plan is then measured by a metric which adds the sum of all action costs and a penalty for each failed soft trajectory constraint. Keyder and Geffner showed that soft goals can be compiled away. We generalize this approach and illustrate a method of compiling soft trajectory constraints into conditional effects and state-dependent action costs using LTL f and deterministic finite automata. We provide two compilation schemes, with and without reward shaping, by rewarding and penalizing different states in the plan. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.
-
Max Waters, Bernhard Nebel, Lin Padgham and Sebastian Sardiña.
Plan Relaxation via Action Debinding and Deordering.
In
Proceedings of International Conference on Automated Planning and Scheduling (ICAPS 2018), pp. 278-287.
2018.
(Show abstract)
(Hide abstract)
(PDF)
While seminal work has studied the problem of relaxing the ordering of a plan’s actions, less attention has been given to the problem of relaxing and modifying a plan’s variable bindings. This paper studies the problem of relaxing a plan into a partial plan which specifies which operators must be executed, but need not completely specify their order or variable bindings. While partial plans can provide an agent with additional flexibility and robustness at execution time, many operations over partial plans are intractable. This paper tackles this problem by proposing and empirically evaluating a fixed-parameter tractable algorithm which searches for tractable, flexible partial plans.
-
Felix Lindner, Robert Mattmüller and Bernhard Nebel.
Moral Permissibility of Action Plans.
In
Proceedings of the ICAPS Workshop on EXplainable AI Planning (XAIP).
2018.
(Show abstract)
(Hide abstract)
(PDF)
Research in classical planning so far was mainly concerned with generating a satisficing or an optimal plan.
However, if such systems are used to make decisions that are relevant to humans, one should also consider
the ethical consequences that generated plans can have. We address this challenge by analyzing in how
far it is possible to generalize existing approaches of machine ethics to automatic planning systems.
Traditionally, ethical principles are formulated in an action-based manner, allowing to judge the execution of
one action. We show how such a judgment can be generalized to plans.
Further, we study the complexity of making ethical judgment about plans.
-
Benedict Wright, Oliver Brunner and Bernhard Nebel.
On the Importance of a Research Data Archive.
In
Proceedings of the eighth Symposium on Educational Advances in Artificial Intelligence (EAAI 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
As research becomes more and more data intensive, managing this data becomes a major challenge in any organization. At university level there is seldom a unified data management system in place. The general approach to storing data in such environments is to deploy network storage. Each member can store their data organized to their own likings in their dedicated location on the network. Additionally, users tend to store data in distributed manner such as on private devices, portable storage, or public and private repositories. Adding to this complexity, it is common for university departments to have high fluctuation of staff, resulting in major loss of information and data on an employee's departure. A common scenario then is that it is known that certain data has already been created via experiments or simulation. However, it can not be retrieved, resulting in a repetition of generation, which is costly and time-consuming. Additionally, as of recent years, publishers and funding agencies insist on storing, sharing, and reusing existing research data. We show how digital preservation can help group leaders and their employees cope with these issues, by introducing our own archival system OntoRAIS.
-
Robert Mattmüller, Florian Geißer, Benedict Wright and Bernhard Nebel.
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning.
In
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects.
In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.
We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.
-
Johannes Aldinger and Bernhard Nebel.
Addendum to 'Interval Based Relaxation Heuristics for Numeric Planning with Action Costs'.
Technical Report 280,
Institut für Informatik, Albert-Ludwigs-Universität Freiburg, 2017.
(Show abstract)
(Hide abstract)
(PDF)
This report contains two theorems and their proofs supplementing
our work published at the 40th German Conference on Artificial
Intelligence under the title 'Interval Based Relaxation
Heuristics for Numeric Planning with Action Costs'.
-
Johannes Aldinger and Bernhard Nebel.
Interval Based Relaxation Heuristics for Numeric Planning
with Action Costs.
In
KI 2017:Advances in Artificial Intelligence (KI 2017), pp. 15-28.
Springer International Publishing 2017.
(Show abstract)
(Hide abstract)
(PDF)
Many real-world problems can be expressed in terms of states and
actions that modify the world to reach a certain goal. Such
problems can be solved by automated planning. Numeric planning
supports numeric quantities such as resources or physical
properties in addition to the propositional variables from
classical planning. We approach numeric planning with heuristic
search and introduce adaptations of the relaxation heuristics
hmax, hadd and hFF to interval
based relaxation frameworks. In contrast to previous approaches,
the heuristics presented in this paper are not limited to
fragments of numeric planning with instantaneous actions (such as
linear or acyclic numeric planning tasks) and support action
costs.
-
Andreas Hertle and Bernhard Nebel.
Identifying Good Poses When Doing Your Household Chores: Creation and Exploitation of Inverse Surface Reachability Maps.
In
Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017).
2017.
(Show abstract)
(Hide abstract)
(PDF)
In current approaches to combined task and motion planning, usually symbolic planning and sampling based motion-planning are integrated. One problem is here to come up with good samples. We address the problem of identifying useful poses for a robot close to working surfaces such as tables or shelves. Our approach is based on reachability inversion which answers the question: where should the robot be located in order to reach a certain object? We extend the concept from point-based objects to flat polygonal surfaces in order to enable the robot to have a a good grasping position for many objects. Our approach allows to quickly sample multiple distinct poses for the robot from an prior computed distribution. Further we show how sampling from an inverse reachability distribution can be integrated into a CTAMP system.
-
F. Burget, L.D.J. Fiederer, D.Kuhner, M.Völker, Johannes Aldinger, R.T. Schirrmeister, C.Do, J.Boedecker, Bernhard Nebel, T.Ball and W.Burgard.
Acting Thoughts: Towards a Mobile Robotic Service Assistant for Users with Limited Communication Skills.
In
Proceedings of the European Conference on Mobile Robotics (ECMR 2017), pp. 385-390.
2017.
(Show abstract)
(Hide abstract)
(PDF)
As autonomous service robots become more affordable and thus
available also for the general public, there is a growing need
for user friendly interfaces to control the robotic
system. Currently available control modalities typically expect
users to be able to express their desire through either touch,
speech or gesture commands. While this requirement is fulfilled
for the majority of users, paralyzed users may not be able to
use such systems. In this paper, we present a novel framework,
that allows these users to interact with a robotic service
assistant in a closed-loop fashion, using only thoughts. The
brain-computer interface (BCI) system is composed of several
interacting components, i.e., non-invasive neuronal signal
recording and decoding, high-level task planning, motion and
manipulation planning as well as environment perception. In
various experiments, we demonstrate its applicability and
robustness in real world scenarios, considering fetch-and-carry
tasks and tasks involving human-robot interaction. As our
results demonstrate, our system is capable of adapting to
frequent changes in the environment and reliably completing
given tasks within a reasonable amount of time. Combined with
high-level planning and autonomous robotic systems, interesting
new perspectives open up for non-invasive BCI-based human-robot
interactions.
-
Robert Mattmüller, Florian Geißer, Benedict Wright and Bernhard Nebel.
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning.
In
Proceedings of the 9th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2017).
2017.
Superseded by the AAAI 2018 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects.
In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.
We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.
-
Felix Lindner, Martin Mose Bentzen and Bernhard Nebel.
The HERA Approach to Morally Competent Robots.
In
Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017).
2017.
(Show abstract)
(Hide abstract)
(PDF)
To address the requirement for autonomous moral decision making, we introduce a software library for modeling hybrid ethical reasoning agents (short: HERA). The goal of the HERA project is to provide theoretically well-founded and practically usable logic-based machine ethics tools for implementation in robots. The novelty is that HERA implements multiple ethical principles like utilitarianism, the principle of double effect, and a Pareto-inspired principle. These principles can be used to automatically assess moral situations represented in a format we call causal agency models. We discuss how to model moral situations using our approach, and how it can cope with uncertainty about moral values. Finally, we briefly outline the architecture of our robot IMMANUEL, which implements HERA and is able to explain ethical decisions to humans.
-
Johannes Aldinger and Bernhard Nebel.
Extended Abstract: Interval Based Relaxation Heuristics for Numeric Planning
with Action Costs.
In
Proceedings of the 10th International Symposium on Combinatorial Search (SoCS 2017), pp. 155-156.
2017.
(Show abstract)
(Hide abstract)
(PDF)
We adapt the relaxation heuristics hmax,
hadd and hFF to interval based numeric
relaxation frameworks, combining them with two different
relaxation techniques and with two different search techniques. In
contrast to previous approaches, the heuristics presented here are
not limited to a subset of numeric planning and support action
costs.
-
Thorsten Engesser, Thomas Bolander, Robert Mattmüller and Bernhard Nebel.
Cooperative Epistemic Multi-Agent Planning for Implicit Coordination.
In
Ghosh, Sujata and Ramanujam and R. (eds.),
Proceedings of the Ninth Workshop on Methods for Modalities (M4M 2017), pp. 75-90.
2017.
(Show abstract)
(Hide abstract)
(Online; PDF)
(BIB)
Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Recently, Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. We extend the DEL-based epistemic planning framework to include perspective shifts, allowing us to define new notions of sequential and conditional planning with implicit coordination. With these, it is possible to solve planning tasks with joint goals in a decentralized manner without the agents having to negotiate about and commit to a joint policy at plan time. First we define the central planning notions and sketch the implementation of a planning system built on those notions. Afterwards we provide some case studies in order to evaluate the planner empirically and to show that the concept is useful for multi-agent systems in practice.
-
Dali Sun, Florian Geißer and Bernhard Nebel.
Towards Effective Localization in Dynamic Environments.
In
Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Localization in dynamic environments is still a challenging problem in robotics – especially if rapid and large changes
occur irregularly. Inspired by SLAM algorithms, our Bayesian approach to this so-called dynamic localization problem
divides it into a localization problem and a mapping problem, respectively. To tackle the localization problem we use
a particle filter, coupled with a distance filter and a scan matching method, which achieves a more robust localization
against dynamic obstacles. For the mapping problem we use an extended sensor model which results in an effective and precise
map update effect. We compare our approach against other localization methods and evaluate the impact the map update effect
has on the localization in dynamic environments.
-
Tim Schulte and Bernhard Nebel.
Trial-based Heuristic Tree-search for Distributed Multi-Agent Planning.
In
Proceedings of the Ninth Annual Symposium on Combinatorial Search (SoCS 2016)
(SoCS 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
We present a novel search scheme for privacy-preserving multi-agent
planning, inspired by UCT search. We compare the presented approach to
classical multi-agent forward search and evaluate it based on benchmarks
from the CoDMAP competition.
-
Tim Schulte and Bernhard Nebel.
Trial-based Heuristic Tree-search for Distributed Multi-Agent Planning.
In
Proceedings of the 4th Workshop on Distributed and Multi-Agent Planning (DMAP 2016)
(DMAP 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
We present a novel search scheme for privacy-preserving multi-agent
planning. Inspired by UCT search, the scheme is based on growing an
asynchronous search tree by running repeated trials through the tree. We
describe key differences to classical multi-agent forward search, discuss
theoretical properties of the presented approach, and evaluate it based on
benchmarks from the CoDMAP competition.
-
Thomas Bolander, Thorsten Engesser, Robert Mattmüller and Bernhard Nebel.
Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination.
In
Proceedings of the ICAPS-2016 Workshop on Distributed and Multi-Agent Planning (DMAP 2016).
2016.
Superseded by the KR18 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Epistemic planning can be used for decision making in multi-agent
situations with distributed knowledge and capabilities. Recent work
proposed a new notion of strong policies with implicit coordination.
With this it is possible to solve planning tasks with joint goals from
a single-agent perspective without the agents having to negotiate about
and commit to a joint policy at plan time. We study how and under which
circumstances the decentralized application of those policies leads to
the desired outcome.
-
Matthias Hengel, Stefan Wölfl and Bernhard Nebel.
Reasoning about general TBoxes with spatial and temporal constraints: Implementation and optimizations.
In
Proceedings of the 29th International Workshop on Description Logics (DL 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
In many applications a reasonable representation of conceptual
knowledge requires the possibility to express spatial or temporal
relations between domain entities. A feasible approach to this is to
consider spatial or temporal constraint systems on concrete domains.
Indeed, Lutz and Milicic (2007) showed that for the description logic
ALC(C) with ω-admissible constraint systems, concept satsifiability
with respect to general TBoxes can be decided by an extension of a
standard ALC tableau algorithm. In this paper we report on a study in
which this tableau method was implemented, optimized, and evaluated.
-
Malte Schilling, Stefan Kopp, Sven Wachsmuth, Britta Wrede, Helge J. Ritter, Thomas Brox, Bernhard Nebel and Wolfram Burgard.
Towards a Multidimensional Perspective on Shared Autonomy.
In
2016 {AAAI} Fall Symposia.
2016.
(Show abstract)
(Hide abstract)
(Online; PDF; PDF)
Shared Autonomy in the traditional sense focuses on the degree of user intervention in the control of artificial systems. We propose to broaden this notion to allow for more interactive scenarios. This requires a shift away from the single system perspective towards the interaction, the participating agents and the cooperation as such. Such a view on the interaction of autonomous agents has to be based on a more fine-grained understanding. Therefore, we extend a differentiation of autonomy into three different levels to interactive tasks as a starting point for a multidimensional perspective on shared autonomy. In particular, we want to point out how this allows for flexible interaction patterns and the negotiation of changing roles in ongoing cooperation.
-
Marco Ragni, Thomas Barkowsky, Bernhard Nebel and Christian Freksa.
Cognitive Space and Spatial Cognition: The SFB/TR 8 Spatial Cognition.
KI 30 (1), pp. 83-88. 2016.
(Show abstract)
(Hide abstract)
(Online; DOI)
Space and time are two of the most fundamental categories any human, animal, or other cognitive agent such as an autonomous robot has to deal with. They need to perceive their environments, make sense of their perceptions, and make interactions as embodied entities with other agents and their environment. The theoretical foundations and practical implications have been investigated from a cognitive perspective (i.e., from an information processing point of view) within the Sonderforschungsbereich/Transregio SFB/TR 8 Spatial Cognition (http://www.sfbtr8.spatial-cognition.de) over the past 12 years jointly by the Universities of Bremen and Freiburg. The research covered fundamental questions: what are the specific requirements of reasoning about space and time, for acting in space, and for any form of interaction including communication in spatio-temporal domains? It has been a success story in all research lines from foundational research to applications of spatial cognition in robotics, interaction and communication. The SFB/TR 8 actually shaped a new research field by extending a previous subfield of cognitive science with its own interdisciplinary techniques.
-
Nicolas Riesterer, Christian Becker-Asano, Julien Hué, Christian Dornhege and Bernhard Nebel.
The Hybrid Agent MARCO.
In
Proceedings of the 16th International Conference on Multimodal Interaction, pp. 80-81.
2014.
(Show abstract)
(Hide abstract)
(PDF)
We present MARCO, a hybrid, chess playing agent equipped with a custom-built robotic arm and a virtual agent’s face displaying emotions. MARCO was built to investigate the hypothesis that hybrid agents capable of displaying emotions make playing chess more personal and enjoyable. In addition, we aim to explore means of achieving emotional contagion between man and machine.
-
Christian Becker-Asano, Kai Oliver Arras and Bernhard Nebel.
Robotic Tele-presence with DARYL in the Wild.
In
Proceedings of the 2nd International Confernce on Human-Agent Interaction, pp. 91-95.
2014.
(Show abstract)
(Hide abstract)
(PDF)
This paper describes the results of a qualitative analysis of questionnaire data collected during a public exhibition of our robotic tele-presence system. In Summer 2013 the mildly humanized robot DARYL could be tried out by the general public during our University’s science fair in the city center. People were given the chance to communicate through the robot with their peers and to perceive the world through the “eyes” and “ears” of the robot by means of a head-mounted display with attached headphones. An operator’s voice was instanta- neously transmitted to the robot’s location and his or her head movements were tracked to enable direct, intuitive control of the robot’s head movements. Twenty-seven people were interviewed in a structured way about their impressions and opinions after having either operated or interacted with the tele-operated robot. A careful analysis of the acquired data reveals a rather positive evaluation of the tele-presence system and interesting opinions about suitable application areas. These findings may guide designers of robotic tele-presence systems, a research area of increasing popularity.
-
Christian Becker-Asano, Eduardo Meneses, Nicolas Riesterer, Julien Hué, Christian Dornhege and Bernhard Nebel.
The Hybrid Agent MARCO: A Multimodal Autonomous Robotic Chess Opponent.
In
Proceedings of the 2nd International Confernce on Human-Agent Interaction, pp. 173-176.
2014.
(Show abstract)
(Hide abstract)
(PDF)
We present MARCO, a hybrid, chess playing agent equipped with a custom-built robotic arm and a virtual agent’s face displaying emotions. MARCO was built to investigate the hypothesis that hybrid agents capable of displaying emo- tions make playing chess more personal and enjoyable. In addition, we aim to explore means of achieving emotional contagion between man and machine.
-
Johannes Löhr, Martin Wehrle, Maria Fox and Bernhard Nebel.
Symbolic Domain Predictive Control.
In
Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), pp. 2315-2321.
AAAI Press 2014.
(Show abstract)
(Hide abstract)
(Online; DOI)
Planning-based methods to guide switched hybrid systems from an initial state into a desired goal region opens an interesting field for control. The idea of the Domain Predictive Control (DPC) approach is to generate input signals affecting both the numerical states and the modes of the system by stringing together atomic actions to a logically consistent plan. However, the existing DPC approach is restricted in the sense that a discrete and pre-defined input signal is required for each action. In this paper, we extend the approach to deal with symbolic states. This allows for the propagation of reachable regions of the state space emerging from actions with inputs that can be arbitrarily chosen within specified input bounds. This symbolic extension enables the applicability of DPC to systems with bounded inputs sets and increases its robustness due to the implicitly reduced search space. Moreover, precise numeric goal states instead of goal regions become reachable.
-
Andreas Hertle, Christian Dornhege, Thomas Keller, Robert Mattmüller, Manuela Ortlieb and Bernhard Nebel.
An Experimental Comparison of Classical, FOND and Probabilistic Planning.
In
Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 297-308.
Springer 2014.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Domain-independent planning in general is broadly applicable to a wide range of tasks.
Many formalisms exist that allow to describe different aspects of realistic problems.
Which one is best is not clear as usually more expressiveness comes with a cost in
planning time. Under the assumption that hard guarantees are not required, users are
faced with a decision between multiple approaches. In this work we study the effect of
nondeterministic action outcomes. As a generic model we use a probabilistic description
in the form of Markov Decision Processes (MDPs). We define abstracting translations
into a classical planning formalism and fully observable nondeterministic (FOND)
planning. Our goal is to give insight into how state-of-the-art systems perform on
different MDP planning domains. We evaluate those MDPs by running state-of-the-art
planning systems on the abstracted formalisms.
-
Christian Freksa, Bernhard Nebel, Mary Hegarty and Thomas Barkowsky (eds.).
Spatial Cognition {IX} - International Conference, Spatial Cognition 2014.
Springer, Bremen, Germany 2014.
-
Dali Sun, Alexander Kleiner and Bernhard Nebel.
Behavior-based Multi-Robot Collision Avoidance.
In
Proceedings of the IEEE International Conference on Robotics and Automation (ICRA-14), pp. 1668-1673.
2014.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Autonomous robot teams that simultaneously disatch transportation tasks are playing a more and more important role in the industry. In this paper we consider the multi-robot motion planning problem in large robot teams and present a decoupled approach by combining decentralized path planning methods and swarm technologies. Instead of a central coordination, a proper behavior which is directly selected according to the context is used by the robot to keep cooperating with others and to resolve path collisions. We show experimentally that the quality of solutions and the scalability of our method are significantly better than those of conventional decoupled path planning methods. Furthermore, compared to conventional swarm approaches, our method can be widely applied in large-scale environments.
-
Christian Becker-Asano, Severin Gustorff, Kai Oliver Arras and Bernhard Nebel.
On the Effect of Operator Modality on Social and Spatial Presence during Teleoperation of a Human-Like Robot.
In
Third Interantional Symposium on New Frontiers in Human-Robot Interaction at AISB50.
2014.
(Show abstract)
(Hide abstract)
(PDF)
With an increasing availability of affordable and effective robotic telepresence systems, key questions in the design of such systems arise, in particular when they aim at untrained users. Previous research regarding telepresence systems has focused on the (mobile) robotic platforms themselves or the differences between virtual as compared to physical representations thereof. The design space of the operator interface, i.e., the operator modality, with its potential impact on presence, however, has not been explored systematically.
This paper reports results of an empirical study investigating how two different operator modalities impact the perceived spatial and social presence of operators in dyadic remote multi-modal interaction. The robot Daryl, used as telepresence medium in our study, features three degrees of freedom in its head unit as well as a stereo camera system. This enabled the transmission of a stereo, first-person perspective, which was used by the operator in combination with a head-mounted display whose movements were tracked to drive the robot’s head. Compared to a previously realized console-based operator interface, our results show significantly higher spatial as well as social presence for the head-mounted display modality while no significant difference in task performance was found. We conclude that for robotic telepresence platforms with mobile head units and stereo camera systems it seems advisable to use a head-mounted display as part of the teleoperation interface in order to provide operators with a particularly immersive remote presence experience.
-
Christian Becker-Asano, Felix Ruzzoli, Christoph Hölscher and Bernhard Nebel.
A Multi-Agent System based on Unity 4 for Virtual Perception and Wayfinding.
Transportation Research Procedia 2, pp. 425-455. 2014.
(Show abstract)
(Hide abstract)
(PDF)
We developed a multi-agent system that is based on the game engine Unity 4 and allows simulating three-dimensional (3D) way- finding behavior of up to 600 airport passengers at a simulation rate of 60 Hz on an average gaming PC. Virtual 3D perception algorithms are implemented so that the agents dynamically check their respective surroundings for visible signs. Each sign is annotated with the direction of one or more exits and with meta-information such as its readability. Thus, based on findings derived from cognitive science experiments, the agents are modeled to sometimes misinterpret this information. Otherwise, they interpret the sign relative to its location and are then steered into the corresponding direction. This simulation framework was also combined with the head-mounted display “Oculus Rift” to let experiment participants find their way in the Virtual Reality environment.
-
Bernhard Nebel and Stefan Wölfl.
Wissensrepräsentation und -verarbeitung.
In
Günther Görz, Josef Schneeberger and Ute Schmid (eds.),
Handbuch der Künstlichen Intelligenz, pp. 105-128.
Oldenbourg Verlag München 2014.
-
Christian Dornhege, Andreas Hertle and Bernhard Nebel.
Lazy Evaluation and Subsumption Caching for Search-Based Integrated Task and Motion Planning.
In
Proceedings of the IROS workshop on AI-based robotics.
2013.
(Show abstract)
(Hide abstract)
(PDF)
State of the art classical planning systems can efficiently solve large symbolic problem instances. Applying classical planning techniques to robotics is possible by in- tegrating geometric reasoning in the planning process. The problems that are solvable in this way are significantly smaller than purely logical formulations as many costly geometric calculations are requested by a planner. Therefore we aim to avoid those calculations while preserving correctness.
We address this problem with efficient caching techniques. Subsumption caching avoids costly computations by caching geometric queries and beyond answering the same queries also considers less or more constrained ones. Additionally, we describe a lazy evaluation technique that pushes applicability checks for successor states performing geometric queries to a later point. As we are interested in the performance of our planner not as a standalone component, but as part of an intelligent robotic system, we evaluate those techniques embedded in an integrated system during real-world mobile manipulation experiments.
-
Tim Niemueller, Nichola Abdo, Andreas Hertle, Gerhard Lakemeyer, Wolfram Burgard and Bernhard Nebel.
Towards Deliberative Active Perception using Persistent Memory.
In
Proceedings of the IROS workshop on AI-based robotics.
2013.
(Show abstract)
(Hide abstract)
(PDF)
Task coordination for autonomous mobile service robots typically involves a substantial amount of background knowledge and explicit action sequences to acquire the relevant information nowadays. We strive for a system which, given a task, is capable of reasoning about task-relevant knowledge to automatically determine whether that knowledge is sufficient. If missing or uncertain, the robot shall decide autonomously on the actions to gain or improve that knowledge. In this paper we present our baseline system implementing the foundations for these capabilities. The robot has to analyze a tabletop scene and increase its object type confidence. It plans motions to observe the scene from multiple perspectives, combines the acquired data, and performs a recognition step on the merged input.
-
Matthias Westphal, Julien Hué, Stefan Wölfl and Bernhard Nebel.
Transition Constraints: A Study on the Computational Complexity of Qualitative Change.
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'13), pp. 1169-1175.
2013.
(Show abstract)
(Hide abstract)
(Online; PDF)
(DBLP)
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-complete in the presence of continuity constraints, even if the satisfiability problem
of its static descriptions is tractable.
-
Christian Becker-Asano, Dali Sun, Corinna N. Scheel, Brunna Tuschen-Caffier and Bernhard Nebel.
Analyzing for emotional arousal in HMD-based head movements during a virtual emergency.
In
Intl. Workshop on Emotion and Computing in conj. with KI2013.
2013.
(Show abstract)
(Hide abstract)
(PDF)
This paper reports on results of a statistical analysis of human players' head-movements. Forty-one participants were asked to cope with an unexpected emergency in a virtual parking lot. Before the virtual reality exposure began, half of the participants watched an emotion-inducing movie clip and the other half an emotionally neutral one. The analysis of the acquired questionnaire data reveals, however, that this emotion induction method seems to have been rather ineffective. Thus, it is not surprising that only very weak between group effects are found when analyzing for differences in head movements around the emergency event. In general, horizontal head movement speed is found to be on average significantly faster during the first fifteen seconds directly after the emergency event as compared to just before and another fifteen seconds later. These findings are in line with previous results of an analysis of the acquired physiological data, further substantiating the conclusions drawn.
-
Christian Becker-Asano, Philip Stahl, Marco Ragni, Jean-Claude Martin, Matthieu Courgeon and Bernhard Nebel.
An affective virtual agent providing embodied feedback in the paired associate task: system design and evaluation.
In
Proc. of the 13th. Intl. Conf. on Intelligent Virtual Agents (IVA 2013), pp. 406-415.
2013.
(Show abstract)
(Hide abstract)
(PDF)
An affective, virtual agent is presented that acts as a teacher in the classical paired associate task. It is explained, why and how the virtual agent framework MARC was combined with the cognitive architecture ACT-R, the affect simulation architecture WASABI, and the voice-synthesis module OpenMARY. The agent's affective feedback capabilities are evaluated through an empirical study, in which participants had to solve association tasks. We expected that (1) the presentation of the task by a (neutral) virtual agent would change a learner's performance and that (2) the additional simulation and expression of emotions would impact a learner's performance as well. Finally, we discuss reasons for the lack of statistically significant differences as well as planned future application scenarios of our affective agent framework.
-
Bernhard Nebel.
Automatic Planning: Making Autonomous Behavior Possible.
In
43. Jahrestagung der Gesellschaft f{\"{u}}r Informatik, Informatik
angepasst an Mensch, Organisation und Umwelt, INFORMATIK 2013.
Springer 2013.
-
Bernhard Nebel, Christian Dornhege and Andreas Hertle.
How Much Does a Household Robot Need To Know In Order To Tidy
Up Your Home?
In
AAAI Workshop on Intelligent Robotic Systems.
AAAI Press 2013.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Although planning for the tasks a household robot has to perform appears to be easy, there exists the problem that the robot is usually uncertain about the state of the household when starting to plan. For example, when getting the order of tidying up the kitchen, the robot does not know what objects it will have to put away and whether there are actually any objects that need to be put away. Furthermore, while sensing operations can provide more information about the environment, things can go wrong when executing an action.
In this paper, we try to identify conditions under which classical planning can be used in a replanning loop in order to solve the planning problem in nondeterminis- tic partially observable open domains. In particular, we will define completeness and soundness of replanning with respect to nondeterministic planning and we will identify a PSPACE-checkable condition that guarantees soundness.
-
Johannes Löhr, Patrick Eyerich, Stefan Winkler and Bernhard Nebel.
Domain Predictive Control Under Uncertain Numerical State
Information.
In
Proceedings of the 23rd International Conference on
Automated Planning and Scheduling (ICAPS13).
2013.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
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.
-
Christian Becker-Asano, Severin Gustorff, Kai Oliver Arras, Kohei Ogawa, Shuichi Nishio, Hiroshi Ishiguro and Bernhard Nebel.
Robot embodiment, operator modality, and social interaction in tele-existence: a project outline.
In
Proceedings of the 8th ACM/IEEE international conference on Human-robot interaction, pp. 79-80.
2013.
(Show abstract)
(Hide abstract)
(PDF)
This paper outlines our ongoing project, which aims to investigate the effects of robot embodiment and operator modality on an operator’s task efficiency and concomitant level of copresence in remote social interaction. After a brief introduction to related work has been given, five research questions are presented. We discuss how these relate to our choice of the two robotic embodiments “DARYL” and “Geminoid F” and the two operator modalities “console interface” and “head-mounted display”. Finally, we postulate that the usefulness of one operator modality over the other will depend on the type of situation an operator has to deal with. This hypothesis is currently being investigated empirically using DARYL at Freiburg University.
-
Kai M. Wurm, Christian Dornhege, Cyrill Stachniss, Bernhard Nebel and Wolfram Burgard.
Coordinating Heterogeneous Teams of Robots using Temporal Symbolic Planning.
Autonomous Robots. 2013.
(Show abstract)
(Hide abstract)
(BIB)
(Online; DOI)
The efficient coordination of a team of heterogeneous robots is an important requirement for exploration, rescue, and disaster recovery missions. In this paper, we present a novel approach to target assignment for heterogeneous teams of robots. It goes beyond existing target assignment algorithms in that it explicitly takes symbolic actions into account. Such actions include the deployment and retrieval of other robots or manipulation tasks. Our method integrates a temporal planning approach with a traditional cost-based planner. The proposed approach was implemented and evaluated in two distinct settings. First, we coordinated teams of marsupial robots. Such robots are able to deploy and pickup smaller robots. Second, we simulated a disaster scenario where the task is to clear blockades and reach certain critical locations in the environment. A similar setting was also investigated using a team of real robots. The results show that our approach outperforms ad-hoc extensions of state-of-the-art cost-based coordination methods and that the approach is able to efficiently coordinate teams of heterogeneous robots and to consider symbolic actions.
-
Christian Becker-Asano, Kai Oliver Arras, Bernhard Nebel and Hiroshi Ishiguro.
The Effect of Anthropomorphism on Social Tele-Embodiment.
In
IROS 2012 Workshop on Human-Agent Interaction.
2012.
(Show abstract)
(Hide abstract)
(PDF)
This paper outlines our approach to explore the impact of using two different robotic embodiments on an oper- ators ability to convey emotional and conversational nonverbal signals to a distant interlocutor. Although a human’s ability to produce and interpret complex, dynamic facial expressions is seen as an important factor for human-human social interac- tion, it remains controversial in humanoid/android robotics, whether recreating such expressiveness is really worth the technical challenge, or not. In fact, one way to avoid the risk of giving rise to uncanny feelings in human observers is to follow an abstract design for humanoid robots. This question is also relevant in the context of mediated interaction using tele-operation technology, as soon as robotic embodiments are involved. Thus, this paper presents our current project, in which we are comparing the efficiency of transmitting nonverbal signals by means of “Daryl” featuring an abstract, mildly humanized design, against that of “Geminoid F”, which features a highly anthropomorphic design. The ability of both of these robots to convey emotions by means of body movements has been successfully evaluated before, but using this ability to transmit nonverbal signals during remote conversation and comparing the resp. efficiencies has not yet been done.
-
Birgit Kleim, Thomas Ehrig, Corinna Scheel, Christian Becker-Asano, Bernhard Nebel and Brunna Tuschen-Caffier.
Bewältigungsverhalten in Notfallsituationen aus klinisch-psychologischer Perspektive.
Zeitschrift für Klinische Psychologie und Psychotherapie 41 (3), pp. 166-179. 2012.
(Show abstract)
(Hide abstract)
(Online; DOI)
Ziel des vorliegenden Beitrags ist es, eine aktuelle Übersicht zu Annahmen und Befunden zu geben, die Hinweise darauf geben, welche Reaktionen bzw. welches Verhalten für die Bewältigung von Notfällen oder traumatischen Erlebnissen hilfreich bzw. gesundheitsförderlich sind. Ließen sich konkrete Aspekte von Bewältigungsverhalten während traumatischer Situationen identifizieren, die besonders adaptiv in Bezug auf die psychische bzw. psychobiologische Anpassung sind, so könnte dieses Wissen perspektivisch zur Entwicklung von Präventions- und Trainingsmaßnahmen genutzt werden. Der Beitrag beschreibt einleitend Traumareaktionen, psychische Traumafolgestörungen und deren Prävalenzraten und gibt eine knappe Übersicht über Prädiktoren für psychische Störungen in Folge traumatischer Erlebnisse. Im Unterschied zu dem Beitrag von Becker-Nehring, Witschen und Bengel (in diesem Heft) fokussiert unser Beitrag vor allem auf die Posttraumatische Belastungsstörung als Traumafolgestörung und auf Bewältigungsverhalten während einer Notfallsituation. Bewältigungsverhalten während und nach einer traumatischen Situation kann zum Teil auch im Forschungslabor experimentell untersucht werden, indem z. B. Methoden der Virtuellen Realität genutzt werden. Dies ist ein weiterer Fokus des Beitrags.
-
Corinna N. Scheel, Birgit Kleim, Julian Schmitz, Christian Becker-Asano, Dali Sun, Bernhard Nebel and Brunna Tuschen-Caffier.
Psychophysiologische Belastungsreaktivität nach einem simulierten Feuer in einer Parkgarage.
Zeitschrift für Klinische Psychologie und Psychotherapie 41 (3), pp. 180-189. 2012.
(Show abstract)
(Hide abstract)
(Online; DOI)
Theoretischer Hindergrund: Bewältigungsverhalten in Notfallsituationen wird meistens retrospektiv erfasst oder ist aufgrund der Verschiedenheit der Notfallsituationen schlecht vergleichbar. Methoden der Virtuellen Realität (VR) ermöglichen die Erfassung von Verhaltensparametern und psychophysiologischen Belastungsreaktionen während eines belastenden Ereignisses und erlauben zudem das standardisierte Wiederholen für mehrere Personen. Fragestellung: Ziel unserer Studie war es, ein neues Notfallszenario (Feuer in einer Parkgarage) in VR zu entwickeln und zu testen, ob sich anhand dessen substanzielle psychische und physiologische Belastungsreaktionen induzieren lassen. Methode: Mehrfach im Untersuchungsablauf wurden das emotionale Erleben und physiologische Parameter erhoben. Ergebnisse: Das VR Szenario führte bei den teilnehmenden Probanden sowohl zu subjektiven als auch zu physiologischen Veränderungen im Sinne einer Stressinduktion. Das von uns entwickelte Szenario erscheint daher brauchbar, Verhaltensstrategien und Bewältigungsverhalten in Notfallsituationen zu simulieren. Schlussfolgerungen: Möglichkeiten und Grenzen der VR-Methode mit Blick auf klinisch-psychologische Implikationen werden diskutiert.
-
Johannes Löhr, Bernhard Nebel and Stefan Winkler.
Planning Based Autonomous Lander Control.
In
Proceedings of the Astrodynamics Specialist Conference (AIAA/AAS 2012).
2012.
(Show abstract)
(Hide abstract)
(Online; DOI)
Safe landing of spacecraft on extraterrestrial surfaces implies a
number of challenges. The main issue is to precisely initiate
coasting, braking and landing maneuvers to safely land at a desired
landing zone. Meanwhile, the increasing information level about the
landing environment has to be processed and the landing trajectory
eventually adapted in order to avoid hazardous situations. In this
paper these time critical tasks are performed by Domain Predictive
Control. It has been developed to guide dynamic systems into desired
goal states by flexibly reordering atomic actions using planning
algorithms from artificial intelligence. Here, the method is applied
to autonomously adapt control commands and associated landing
trajectories with respect to the changing environmental knowledge.
Simulation results show the feasibility of this new approach and
reveal issues which should be subject to future research.
-
Johannes Löhr, Patrick Eyerich, Thomas Keller and Bernhard Nebel.
A Planning Based Framework for Controlling Hybrid Systems.
In
Proceedings of the 22nd International Conference on
Automated Planning and Scheduling (ICAPS
2012).
2012.
(Show abstract)
(Hide abstract)
(PDF)
The control of dynamic systems, which aims to minimize the
deviation of state variables from reference values in a contin-
uous state space, is a central domain of cybernetics and con-
trol theory. The objective of action planning is to find
feasible state trajectories in a discrete state space from an
initial state to a state satisfying the goal conditions, which
in principle ad- dresses the same issue on a more abstract
level. We combine these approaches to switch between dynamic
system charac- teristics on the fly, and to generate control
input sequences that affect both discrete and continuous state
variables. Our approach (called Domain Predictive Control) is
applicable to hybrid systems with linear dynamics and
discretizable inputs.
-
Andreas Hertle, Christian Dornhege, Thomas Keller and Bernhard Nebel.
Planning with Semantic Attachments: An Object-Oriented View.
In
Proceedings of the European Conference on Artificial Intelligence (ECAI).
2012.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In recent years, domain-independent planning has been applied to
a rising number of real-world applications. Usually, the
description language of choice is PDDL. However, PDDL is not
suited to model all challenges imposed by real-world
applications. Dornhege et al. proposed semantic attachments to
allow the computation of Boolean fluents by external processes
called modules during planning. To acquire state information
from the planning system a module developer must perform manual
requests through a callback interface which is both
inefficient and error-prone.
In this paper, we present the Object-oriented Planning Language
OPL, which incorporates the structure and advantages of modern
object-oriented programming languages. We demonstrate how a
domain-specific module interface that allows to directly access
the planner state using object member functions is automatically
gen- erated from an OPL planning task. The generated
domain-specific interface allows for a safe and less error-prone
implementation of modules. We show experimentally that this
interface is more efficient than the PDDL-based module interface
of TFD/M.
-
Bernhard Nebel.
Editorial.
In
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.),
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments, pp. 45-47.
Springer 2012.
(Show abstract)
(Hide abstract)
(Online;DOI)
Each practically meaningful service robot has a set of skills such as sensing and interpreting its environment, manipulating objects, moving around or communicating with humans. However, even if all these skills are implemented, there is still the problem of applying the right skill - or the right combination of skills - at the right point in time. One way to address this issue is to employ an action planner.
-
Paul-Gerhard Plöger, Kai Pervölz, Christoph Mies, Patrick Eyerich, Michael Brenner and Bernhard Nebel.
Component Based Architecture for an Intelligent Mobile Manipulator.
In
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.),
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments, pp. 19-42.
Springer 2012.
(Show abstract)
(Hide abstract)
(Online;DOI)
We describe the development of an architecture for the DESIRE technology demonstrator based on principles of classical component based software engineering. The architecture is directly derived from the project requirements and resides on the concept of an Autonomous Component utilizing a smart feedback value called WishLists. This return type is able to provide expert advice about the reasons of occurring failures and give hints for possible recovery strategies. This is of key importance to advance towards robustness. The integration of an AI task planner allows the realization of higher flexibility, dependability and capability during task execution and may resolve conflicts between occurring WishLists. Furthermore the necessity of a central system-state model (Eigenmodel), which represents the current state and configuration of the whole system at runtime, is explained and illustrated. We conclude with some lessons learned.
-
Michael Brenner and Bernhard Nebel.
Proactive Continual Planning -- Deliberately Interleaving Planning and Execution in Dynamic Environments.
In
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.),
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments, pp. 65-75.
Springer 2012.
(Show abstract)
(Hide abstract)
(Online;DOI)
In order to behave intelligently, artificial agents must be able to deliberatively plan their future actions. Unfortunately, realistic agent environments are usually highly dynamic and only partially observable, which makes planning computationally hard. For most practical purposes this rules out planning techniques that account for all possible contingencies in the planning process. However, many agent environments permit an alternative approach, namely continual planning, i. e. the interleaving of planning with acting and sensing.
This article presents a principled approach to continual planning that describes why and when an agent should switch between planning and acting. The resulting continual planning algorithm enables agents to deliberately postpone parts of their planning process and instead actively gather missing information that is relevant for the later refinement of the plan. To this end, the algorithm explictly reasons about the knowledge (or lack thereof) of an agent and its sensory capabilities. In order to enable proactive information gathering we introduce the concept of assertions into our planning language, i.e. abstract actions that can substitute yet unformed subplans in early planning phases.
To study our continual planning approach empirically we have developed MAPSIM, a simulation environment that automatically builds multiagent simulations from planning domain descriptions. In MAPSIM, agents can thus not only plan, but also execute their plans, perceive their environment, and interact with each other.While obviously such a simulation does not capture many aspect of a physical robot environment, it can be used for rapid prototyping of planning models for such environments.
-
Michael Brenner and Bernhard Nebel.
Continual Multiagent Planning.
In
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.),
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments, pp. 77-97.
Springer 2012.
(Show abstract)
(Hide abstract)
(Online;DOI)
In this article, we extend the Continual Planning approach presented in the preceding article to multiagent settings. In principle, the presence of other agents increases the dynamics and uncertainty of an environment. As a result, planning in such domains becomes computationally much harder. We argue, however, that collaborative agents can overcome this complexity by proactively striving to exchange knowledge and collaborating on subproblems. The article gives an overview about the planning language MAPL that enables agents to explicitly reason about their own and others’ sensory and communicative capabilities, their beliefs and mutual beliefs, and about the necessary conditions for joint behaviour. Based on this, we describe the Continual Collaborative Planning algorithm (CCP), a distributed algorithm for autonomous agents planning and acting in multiagent worlds. We then present empirical evidence of the effectiveness of our approach in a prototypical highly-dynamic multiagent system. Finally we discuss in depth several possible applications, e.g. the use of CCP in Human-Robot Interaction and in a robot able to extend its domain knowledge on-the-fly, i.e. while acting in the environment.
-
Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner and Bernhard Nebel.
Semantic Attachments for Domain-Independent Planning Systems.
In
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.),
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments, pp. 99-115.
Springer 2012.
(Show abstract)
(Hide abstract)
(Online;DOI)
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.
-
Thomas Keller, Patrick Eyerich and Bernhard Nebel.
Task Planning for an Autonomous Service Robot.
In
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.),
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments, pp. 117-124.
Springer 2012.
(Show abstract)
(Hide abstract)
(Online;DOI)
In the DESIRE project, an autonomous robot capable of performing service tasks in a typical kitchen environment has been developed. The overall system consists of various loosely coupled subcomponents providing particular features like manipulating objects or recognizing and interacting with humans. To bring all these subcomponents together to act as monolithic system, a high-performance planning system has been implemented. In this paper, we present this system’s basic architecture and some advanced extensions necessary to cope with the various challenges arising in dynamic and uncertain environments like those a real world service robot is usually faced with.
-
Erwin Prassler, Johann Marius Zöllner, Rainer Bischoff, Wolfram Burgard, Robert Haschke, Martin Hägele, Gisbert Lawitzky, Bernhard Nebel, Paul-Gerhard Plöger and Ulrich Reiser (eds.).
Towards Service Robots for Everyday Environments - Recent Advances in Designing Service Robots for Complex Tasks in Everyday Environments.
Volume 76 of Springer Tracts in Advanced Robotics.
Springer 2012.
(Online;DOI)
-
Jens Claßen, Gabriele Röger, Gerhard Lakemeyer and Bernhard Nebel.
PLATAS – Integrating Planning and the Action Language Golog.
KI – Künstliche Intelligenz 26, pp. 61-67. 2012.
(Authors' preprint. The final publication is available at
www.springerlink.com.).
(Show abstract)
(Hide abstract)
(PDF)
Action programming languages like Golog allow to define complex
behaviors for agents on the basis of action representations in terms of
expressive (first-order) logical formalisms, making them suitable for
realistic scenarios of agents with only partial world knowledge. Often
these scenarios include sub-tasks that require sequential planning.
While in principle it is possible to express and execute such planning
sub-tasks directly in Golog, the system can performance-wise not
compete with state-of-the-art planners. In this paper, we report on our
efforts to integrate efficient planning and expressive action
programming in the Platas project. The theoretical foundation is laid
by a mapping between the planning language Pddl and the Situation
Calculus, which is underlying Golog, together with a study of how these
formalisms relate in terms of expressivity. The practical benefit is
demonstrated by an evaluation of embedding a Pddl planner into Golog,
showing a drastic increase in performance while retaining the full
expressiveness of Golog.
-
Alexander Kleiner, Bernhard Nebel and V.A. Ziparo.
A Mechanism for Dynamic Ride Sharing based on Parallel Auctions.
In
Proc. of the 22th International Joint Conference on Artificial Intelligence (IJCAI).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
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. Ex- isting 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 minimize 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 feature 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.
-
Christian Becker-Asano, Dali Sun, Birgit Kleim, Corinna Scheel, Brunna Tuschen-Caffier and Bernhard Nebel.
Outline of an Empirical Study on the Effects of Emotions on Strategic Behavior in Virtual Emergencies.
In
Affective Computing and Intelligent Interaction, pp. 508-517.
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The applicability of appropriate coping strategies is important in emergencies or traumatic experiences such as car accidents or human violence. In this context, emotion regulation and decision making are relevant. However, research on human reactions to traumatic experiences is very challenging and most existing research uses retrospective assessments of these variables of interest. Thus, we are currently developing and evaluating novel methods to investigate human behavior in cases of emergency. Virtual reality scenarios of emergencies are employed to enable an immersive interactive engagement (e.g., dealing with fire inside a building) based on the modification of Valve’s popular Source 2007 game engine.
This paper presents our ongoing research project, which aims at the empirical investigation of human strategic behavior under the influence of emotions while having to cope with virtual emergencies.
-
Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
On Qualitative Route Descriptions: Representation and
Computational Complexity.
In
Proceedings of the 22nd International Joint
Conference on Artificial Intelligence
(IJCAI 2011), pp. 1120-1125.
AAAI Press 2011.
(Show abstract)
(Hide abstract)
(Online; PDF)
The generation of route descriptions is a fundamental
task of navigation systems. A particular problem in this context
is to identify routes that can easily be described and processed
by users. In this work, we present a framework for representing
route networks with the qualitative information necessary to
evaluate and optimize route descriptions with regard to
ambiguities in them. We identify different agent models that
differ in how agents are assumed to process route descriptions
while navigating through route networks. Further, we analyze the
computational complexity of matching route descriptions and paths
in route networks in dependency of the agent model. Finally we
empirically evaluate the influence of the agent model on the
optimization and the processing of route instructions.
-
Antje Krumnack, Leandra Bucher, Jelica Nejasmic, Bernhard Nebel and Markus Knauff.
A model for relational reasoning as verbal reasoning.
Cognitive Systems Research 12 (3-4), pp. 377-392. 2011.
(Show abstract)
(Hide abstract)
(Online; DOI)
Deductive reasoning is an essential part of complex cognition. It occurs whenever human beings (or machines) draw conclusions that go beyond what is explicitly provided. Reasoning about spatial relations is an excellent testbed for the assessment of competing reasoning theories. In the present paper we show that such competing theories are often less diverse than one might think. We introduce an approach for how relational reasoning can be conceived as verbal reasoning. We describe a theory of how humans construct a one-dimensional mental representation given spatial relations. In this construction process objects are inserted in a dynamic structure called a “queue” which provides an implicit direction. The spatial interpretation of this direction can theoretically be chosen freely. This implies that choices in the process of constructing a mental representation influence the result of deductive spatial reasoning. To derive the precise rules for the construction process we employ the assumption that humans try to minimize their cognitive effort, and two cost measures are compared to judge the efficiency of the construction process. From this we deduce how the queue should be constructed. We discuss empirical evidence for this approach and provide algorithms for a computational implementation of the construction and reasoning process.
-
Bernhard Nebel and Christian Freksa.
AI Approaches to Cognitive Systems – The Example of Spatial Cognition.
Informatik-Spektrum 34 (5), pp. 462-468. 2011.
(Show abstract)
(Hide abstract)
(PDF)
Cognitive abilities can be studied by observing and inter- preting natural systems or by developing artificial systems that interact with their environments in intelligent ways. Cognitive systems research connects both approaches. Typically, human requirements are in the fo- cus of interest and systems are developed to interact with humans in as natural ways as possible. To achieve this goal, a deep understanding of human cognition is required. The present paper focuses on spatial cog- nition, i.e. the ability of perceiving and conceiving spatial environments and solving spatial tasks intelligently. It discusses artificial intelligence approaches to spatial cognition for supporting human activities.
-
Cai Zhongjie, Dapeng Zhang and Bernhard Nebel.
Playing Tetris Using Bandit-Based Monte-Carlo Planning.
In
Proceedings of AISB 2011 Symposium: AI and Games (AISB 2011).
2011.
(Show abstract)
(Hide abstract)
(PDF)
Tetris is a stochastic, open-ended board game. Existing artificial
Tetris players often use different evaluation functions and plan for
only one or two pieces in advance. In this paper, we developed an
artificial player for Tetris using the bandit-based Monte-Carlo
planning method (UCT).
In Tetris, game states are often revisited. However, UCT does not keep
the information of the game states explored in the previous planning
episodes. We created a method to store such information for our player
in a specially designed database to guide its future planning
process. The planner for Tetris has a high branching factor. To
improve game performance, we created a method to prune the planning
tree and lower the branching factor.
The experiment results show that our player can successfully play
Tetris, and the performance of our player is improved as the number of
the played games increases. The player can defeat a benchmark player
with high probabilities.
-
Matthias Westphal, Christian Dornhege, Stefan Wölfl, Marc Gissler and Bernhard Nebel.
Guiding the Generation of Manipulation Plans by Qualitative Spatial Reasoning.
Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), pp. 75-102. 2011.
(Show abstract)
(Hide abstract)
(Online; DOI)
(BIB)
Manipulation planning is a complex task for robots with a manipulator arm that need to grasp objects in the environment, specifically under narrow spatial conditions restricting the workspace of the robot. A popular approach for generating motion plans is probabilistic roadmap planning. However, the sampling strategy of such planners is usually unguided, and hence may lead to motion plans that seem counterintuitive for a human observer. In this article we present an approach that generates heuristics for the probabilistic sampling strategy from spatial plans that abstract from concrete metric data. These spatial plans describe a free trajectory in the workspace of the robot on a purely qualitative level, i.e., by employing spatial relations from formalisms considered in the domain of Qualitative Spatial and Tem- poral Reasoning. We discuss how such formalisms and constraint-based reasoning methods can be applied to approximate geometrically feasible motions. The paper is completed by an evaluation of a hybrid planning system in different spatial settings showing that run-times are notably improved when an abstract plan is considered as a guidance heuristic.
-
Dapeng Zhang and Bernhard Nebel.
Feature Induction of Linear-Chain Conditional Random Fields - A Study Based on a Simulation.
In
Proceedings of the 3rd International Conference on Agents and Artificial Intelligence (ICAART 2011).
2011.
(Show abstract)
(Hide abstract)
(PDF)
Conditional Random Fields (CRFs) is a probabilistic framework for labeling sequential data. Several approaches
were developed to automatically induce features for CRFs. They have been successfully applied in
real-world applications, e.g. in natural language processing. The work described in this paper was originally
motivated by processing the sequence data of table soccer games. As labeling such data is very time consuming,
we developed a sequence generator (simulation), which creates an extra phase to explore several basic
issues of the feature induction of linear-chain CRFs. First, we generated data sets with different configurations
of overlapped and conjunct atomic features, and discussed how these factors affect the induction. Then, a
reduction step was integrated into the induction which maintained the prediction accuracy and saved the computational
power. Finally, we developed an approach which consists of a queue of CRFs. The experiments
show that the CRF queue achieves better results on the data sets in all the configurations.
-
Martin Lames, Tim McGarry, Bernhard Nebel and Karen Roemer (eds.).
Computer Science in Sport - Special emphasis: Football (Dagstuhl Seminar 11271).
Technical Report ,
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), 2011.
(Show abstract)
(Hide abstract)
(Online;DOI)
This report documents the program and the outcomes of Dagstuhl Seminar 11271 ``Computer Science in Sport - Special emphasis: Football''. There were five sessions over the course of three days focusing on separate specific aspects on the relevance, applications and current issues pertaining to computer science in sport. The first session on the first day was about RoboCup -- the history, types of games and robots used, and the current topics relevant to machine learning, tracking and planning. The second session on the first day was a miscellaneous session, which looked at broad topics ranging from hardware devices for mobile coaching, uses of positional data in football, rehabilitation methodologies and games for learning. The second day started with a session on modelling sports as dynamical systems combined with the use of neural networks in performance analysis as well as theoretical issues in human movement science. In the afternoon of the second day the session was on topics in computer science specifically relevant to coaches, in which six different people presented. The final day of the conference hosted a session on computer science ``behind the scenes'' of major sports broadcasters and other media. The sessions were attended by academics, graduate students, coaches, performance analysts and athletes.
-
Brunna Tuschen-Caffier, Birgit Kleim, Christian Becker-Asano, Dali Sun, Bernhard Nebel and Corinna Scheel.
Bewältigungsverhalten in virtuellen Notfallsituationen.
In
7. Workshop Kongress für Psychologie und Psychotherapie.
2011.
(BIB)
-
Christian Becker-Asano, Dali Sun, Birgit Kleim, Corinna N. Scheel, Brunna Tuschen-Caffier and Bernhard Nebel.
CoVE: Coping in Virtual Emergencies.
In
Workshop on Emotion and Computing - Current Research and Future Impact, p. 1.
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The applicability of appropriate coping strategies is important in emergencies or traumatic experiences such as car accidents or human violence. However, research on human reactions to traumatic experiences is very challenging and most existing research uses retrospective assessments of these variables of interest. Thus, we are currently developing and evaluating novel methods to investigate human behavior in cases of emergency. Virtual Reality (VR) scenarios of emergencies are employed to enable an immersive interactive engagement (e.g., dealing with fire inside a building) based on the modification of Valve’s popular Source 2007 game engine.
Preliminary results of a first empirical study (cp. Figure 1) suggest that our VR scenario has a similar fear-inducing effect as a short movie clip (Becker- Asano, Sun, Kleim, Scheel, Tuschen-Caffier, and Nebel, 2011), which previously has been evaluated to induce fear. In addition, the neutral VR experiences during the training sessions did never elicit fear in our participants, letting us conclude that the interactively presented emergency itself was indeed the fear eliciting factor in the experimental sessions. In the long run, we aim at a more detailed analysis that includes the personality questionnaire and physiological data, which will be analyzed in correlation with the trajectories of the participants in the VR emergency.
-
Dapeng Zhang, Cai Zhongjie and Bernhard Nebel.
Playing Tetris Using Learning by Imitation.
In
Proceedings of the 11th annual European Conference on Simulation and AI in Computer Games (GAMEON 2010).
2010.
(Show abstract)
(Hide abstract)
(PDF)
Tetris is a stochastic and open-end board game. Several
artificial players were developed to automatically play Tetris.
These players perform well in single games. In this paper,
we developed a platform based on an open source project for
game competitions among multiple players. We develop an
artificial player employed learning by imitation, which is novel
in Tetris. The imitation tasks of playing Tetris were mapped
to a standard data classification problem. The experiments
showed that the performance of the player can be significantly
improved when our player acquires similar game skills as those
of the imitated human. Our player can play Tetris in diverse
ways by imitating different players, and has chances to defeat
the best-known artificial player in the world. The framework
supports incremental learning because the artificial player can
find stronger players and imitate their skills.
-
Kai M. Wurm, Christian Dornhege, Patrick Eyerich, Cyrill Stachniss, Bernhard Nebel and Wolfram Burgard.
Coordinated Exploration with Marsupial Teams of Robots using Temporal Symbolic Planning.
In
Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010).
2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The problem of autonomously exploring an environment with a team
of robots received considerable attention in the past. However,
there are relatively few approaches to coordinate teams of
robots that are able to deploy and retrieve other
robots. Efficiently coordinating the exploration with such
marsupial robots requires advanced planning mechanisms that are
able to consider symbolic deployment and retrieval actions. In
this paper, we propose a novel approach for coordinating the
exploration with marsupial robot teams. Our method integrates a
temporal symbolic planner that explicitly considers deployment
and retrieval actions with a traditional cost-based assignment
procedure. Our approach has been implemented and evaluated in
several simulated environments and with varying team sizes. The
results demonstrate that our proposed method is able to
coordinate marsupial teams of robots to efficiently explore
unknown environments.
-
Thomas Keller, Patrick Eyerich and Bernhard Nebel.
Task Planning for an Autonomous Service Robot.
In
Rüdiger Dillmann, Jürgen Beyerer, Uwe Hanebeck and Tanja Schultz (eds.),
Proceedings on the 33rd Annual German Conference on Artificial Intelligence (KI 2010), pp. 358-365.
Springer-Verlag 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In the DESIRE project an autonomous robot capable of performing service tasks in a typical kitchen environment has been developed. The overall system consists of various loosely coupled subcomponents providing particular features like manipulating objects or recognizing and interacting with humans. To bring all these subcomponents together to act as monolithic system, a high-performance planning system has been implemented. In this paper, we present this system’s basic architecture and some advanced extensions necessary to cope with the various challenges arising in dynamic and uncertain environments like those a real world service robot is usually faced with.
-
Christian Dornhege, Patrick Eyerich, Thomas Keller, Michael Brenner and Bernhard Nebel.
Integrating Task and Motion Planning Using Semantic Attachments.
In
24th AAAI Workshop: Bridging the Gap Between Task and Motion Planning.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
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, the change of fluents and the calculation of durations by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into forward-chaining planning systems and report on our experience of adding this extension to the planner Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.
-
Christian Freksa, Holger Schultheis, Kerstin Schill, Thora Tenbrink, Thomas Barkowsky, Christoph Hölscher and Bernhard Nebel.
Spatial Cognition: Reasoning, Action, Interaction.
Künstliche Intelligenz 24 (4). 2010.
(Show abstract)
(Hide abstract)
(Online;DOI)
The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT.
We propose a simple and easy to implement procedure, which finds solutions of length O(knc + n^2), where n is the number of nodes, k is the number of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n^3), which is equal to our result in the worst case, but does not capture the dependency on c and k.
-
Moritz Göbelbecker, Thomas Keller, Patrick Eyerich, Michael Brenner and Bernhard Nebel.
Coming Up with Good Excuses: What To Do When No Plan Can be Found.
In
Ronen Brafman, Héctor Geffner, Jörg Hoffmann and Henry Kautz (eds.),
Proceedings of the 20th International Conference on Automated Planning and Scheduling
(ICAPS 2010), pp. 81-88.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
When using a planner-based agent architecture, many things can
go wrong. First and foremost, an agent might fail to execute
one of the planned actions for some reasons. Even more
annoying, however, is a situation where the agent is
incompetent, i.e., unable to come up with a plan. This
might be due to the fact that there are principal reasons that
prohibit a successful plan or simply because the task's
description is incomplete or incorrect. In either case, an
explanation for such a failure would be very helpful. We will
address this problem and provide a formalization of coming
up with excuses for not being able to find a plan. Based
on that, we will present an algorithm that is able to find
excuses and demonstrate that such excuses can be found in
practical settings in reasonable time.
-
Patrick Eyerich, Thomas Keller and Bernhard Nebel.
Combining Action and Motion Planning via Semantic Attachments.
In
Proceedings of the Workshop on Combining Action and Motion Planning at ICAPS 2010
(CAMP 2010), p. 19.
2010.
Extended Abstract.
(PDF)
(BIB)
-
Michael Brenner, Christian Plagemann, Bernhard Nebel, Wolfram Burgard and Nick Hawes.
Planning and Failure Detection.
In
Henrik Iskov Christensen, Geert-Jan M. Kruijff and Jeremy L. Wyatt (eds.),
Cognitive Systems, pp. 223-264.
Springer 2010.
(Show abstract)
(Hide abstract)
(Online;DOI)
The capacity for planful behavior is one of the major characteristics of an intelligent agent. When acting in realistic environments, however, reasoning about how to achieve one’s goals is complicated significantly, both by the limited perceptions of the agent and the high dynamics of the environment, especially when other intelligent agents are present. Fortunately, when acting continuously in such an environment, agents can actively try to reduce their uncertainties, for example by deliberative exploration, cooperation with others, and monitoring of failures.
-
Marc Gissler, Christian Dornhege, Bernhard Nebel and Matthias Teschner.
Deformable Proximity Queries and their Application in Mobile Manipulation Planning.
In
Symposium on Visual Computing (ISVC 2009), pp. 79-88.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We describe a proximity query algorithm for the exact minimum distance computation between arbitrarily shaped objects. Special characteristics of the Gilbert-Johnson-Keerthi (GJK) algorithm are employed in various stages of the algorithm. In the first stage, they are used to search for sub-mesh pairs whose convex hulls do not intersect. In the case of an intersection, they guide a recursive decomposition. Finally, they are used to derive lower and upper distance bounds in non-intersecting cases. These bounds are utilized in a spatial subdivision scheme to achieve a twofold culling of the domain. The algorithm does not depend on spatial or temporal coherence and is, thus, specifically suited to be applied to deformable objects. Furthermore, we describe its embedding into the geometrical part of a mobile manipulation planning system. Experiments show its usability in dynamic scenarios with deformable objects as well as in complex manipulation planning scenarios.
-
Christian Dornhege, Marc Gissler, Matthias Teschner and Bernhard Nebel.
Integrating Symbolic and Geometric Planning for Mobile Manipulation.
In
IEEE International Workshop on Safety, Security and Rescue Robotics
(SSRR 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Mobile manipulation requires to solve multiple subproblems.
One is planning in high-dimensional configuration spaces, that we approach in this work.
We decompose the manipulation problem into a symbolic and a geometric part.
The symbolic part is implemented as a classical symbolic planner that
tightly integrates a geometric planner enabling us to efficiently generate correct
plans.
A probabilistic roadmap planner constitutes the geometric part.
During the computation of the roadmap we utilize proximity queries to determine non-colliding configurations and to verify collision-free paths between configurations accurately and efficiently.
We demonstrate experiments in two scenarios, one of these being the manipulator dexterity test scenario that was
used in NIST's response robot evaluation in Disaster City.
-
Dapeng Zhang, Cai Zhongjie, Chen Kefei and Bernhard Nebel.
A Game Controller Based on Multiple Sensors.
In
In Proceedings of the Fifth International Conference on Advances in Computer Entertainment Tochnology (ACE 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
A digital game is normally controlled by hand. Playing such
a game requires only minimum hand movements. Rather
than being easy and comfortable, this game controller is designed
to be physically taxing for the players. It consists of
several sensors, which makes a game more lively and forces
the users to be more physically active. By using different
mapping methods, one game can be played in several ways.
The statistics gathered from the experiments show that even
though the quality of control on the chosen fighting game is
not as high as with a normal joystick, the developed controller
is still preferred by most of the participants. It induces
much more movement than a normal joystick.
-
Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner and Bernhard Nebel.
Semantic Attachments for Domain-Independent Planning Systems.
In
Proceedings of the 19th International Conference on Automated
Planning and Scheduling (ICAPS 2009), pp. 114-121.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
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.
-
Michael Brenner and Bernhard Nebel.
Continual Planning and Acting in Dynamic Multiagent Environments.
Journal of Autonomous Agents
and Multiagent Systems 19 (3), pp. 297-331. 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In order to behave intelligently, artificial agents must be able
to deliberatively plan their future actions. Unfortunately,
realistic agent environments are usually highly dynamic and only
partially observable, which makes planning computationally hard. For
most practical purposes this rules out planning techniques that
account for all possible contingencies in the planning process.
However, many agent environments permit an alternative approach,
namely continual planning, i.e. the interleaving of planning with
acting and sensing.
This paper presents a new principled approach to continual
planning that describes why and when an agent should switch between
planning and acting. The resulting continual planning algorithm
enables agents to deliberately postpone parts of their planning
process and instead actively gather missing information that is
relevant for the later refinement of the plan. To this end, the
algorithm explictly reasons about the knowledge (or lack thereof) of
an agent and its sensory capabilities. These concepts are modelled
in the planning language MAPL. Since in many environments the major
reason for dynamism is the behaviour of other agents, MAPL can also
model multiagent environments, common knowledge among agents, and
communicative actions between them. For Continual Planning, MAPL
introduces the concept of of assertions, abstract actions that
substitute yet unformed subplans.
To evaluate our continual planning approach empirically we have
developed MAPSIM, a simulation environment that automatically builds
multiagent simulations from formal MAPL domains. Thus, agents can
not only plan, but also execute their plans, perceive their
environment, and interact with each other. Our experiments show
that, using continual planning techniques, deliberate action planning
can be used efficiently even in complex multiagent environments.
-
Jie Bao, Uldis Bojars, Tanzeem Choudhury, Li Ding, Mark Greaves, Ashish Kapoor, Sandy Louchart, Manish Mehta, Bernhard Nebel, Sergei Nirenburg, Tim Oates, David L. Roberts, Antonio Sanfilippo, Nenad Stojanovic, Kristen Stubbs, Andrea Lockerd Thomaz, Katherine M. Tsui and Stefan Wölfl.
Reports of the AAAI 2009 Spring Symposia.
AI Magazine. 2009.
(Show abstract)
(Hide abstract)
(Online; DOI)
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 symposium 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.
-
Bernhard Nebel and Jochen Renz.
A fixed-parameter tractable algorithm for spatio-temporal calendar management.
In
Proceedings of the 21th International Joint Conference
on Artificial Intelligence (IJCAI 2009), pp. 879--884.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(Online; PDF)
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 re-visited from some other task, a parameter which is small in the application scenario we consider.
-
Bernhard Nebel and Stefan Wölfl.
Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
2009.
AAAI Technical Report SS-09-02.
(Show abstract)
(Hide abstract)
(Online; AAAI)
Over the past 25 years the domain of qualitative spatial and temporal reasoning has evolved to an established subfield of AI. Qualitative reasoning aims at the development of formalisms that are close to conceptual schematas used by humans for reasoning about their physical environment, in particular, about temporal and spatial information. Application fields of qualitative reasoning include human-machine interaction, high-level agent control, geographic information systems, spatial planning, ontological reasoning, and cognitive modeling.
To foster real-world applications, representation and reasoning methods used in qualitative reasoning need to be tested against evaluation criteria adapted from other AI fields and cognitive science. The aim of the symposium was to boost the development of well-founded and widely accepted evaluation standards and practical benchmark problems. This includes the measures to compare different qualitative formalisms in terms of cognitive adequacy, expressiveness, and computational efficiency; the development of a domain and problem specification language for benchmarking purposes; the identification of significant benchmark domains and problem instances based on natural use cases, as well as the creation of a problem repository; and the measures to evaluate the performance of implemented reasoning systems. The symposium fostered the benchmarking idea in the qualitative reasoning domain, contributed to identify a graded set of challenges for future research, and pushed the development of qualitative reasoning methods and systems towards application-relevant problems.
-
Paul Plöger, Kai Pervölz, Christoph Mies, Patrick Eyerich, Michael Brenner and Bernhard Nebel.
The DESIRE Service Robotics Initiative.
Künstliche Intelligenz 08 (4), pp. 29-32. 2008.
(Show abstract)
(Hide abstract)
(PDF)
We present some advanced hardware units and an appropriate
component based SW architecture for DESIRE. As an example we
describe the integration of a enhanced AI task planner which
allows for higher flexibility and dependability during complex
task execution.
-
Patrick Eyerich, Michael Brenner and Bernhard Nebel.
On the Complexity of Planning Operator Subsumption.
In
Proceedings of the Eleventh International Conference on
Principles of Knowledge Representation and Reasoning
(KR
2008), pp. 518-527.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Formal action models play a central role in several subfields of
AI because they are used to model application domains, e.g., in
automated planning. However, there are hitherto no automated
methods for relating such domain models to each other, in
particular for checking whether one is a specialization or
generalization of the other. In this paper, we introduce two kinds
of subsumption relations between operators, both of which are
suitable for modeling and verifying hierarchies between actions
and operators: applicability subsumption considers an action to be
more general than another if the latter can be replaced by the
first at each point in each sound sequence of actions; abstraction
subsumption exploits relations between actions from an ontological
point of view. For both kinds of subsumption, we prove complexity
results for verifying operator subsumption in three important
subclasses: The problems are NP-complete when the expressiveness
of the operators is restricted to the well-known basic STRIPS
formalism, Sigma_p_2-complete when we admit boolean logical operators
and undecidable when the full power of the planning language ADL
is permitted.
-
Gabriele Röger, Malte Helmert and Bernhard Nebel.
On the Relative Expressiveness of ADL and Golog: The Last
Piece in the Puzzle.
In
Proceedings of the Eleventh International Conference on
Principles of Knowledge Representation and Reasoning
(KR
2008), pp. 544-550.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
Integrating agent programming languages and efficient action
planning is a promising approach because it combines the
expressive power of languages such as Golog with the possibility
of searching for plans efficiently. In order to integrate a
Golog interpreter with a planner, one has to understand,
however, which part of the expressiveness of Golog can be
captured by the planning language. Using Nebel's compilation
framework, we identify a maximal fragment of basic action
theories, the formalism Golog is based on, that is
expressively equivalent to the ADL subset of PDDL. As we will
show, almost all features that permit to specify incomplete
information in basic action theories cannot be compiled to ADL.
-
Jussi Rintanen, Bernhard Nebel, J. Christopher Beck and Eric Hansen (eds.).
Proceedings of the 18th International Conference on Automated
Planning and Scheduling
(ICAPS 2008).
AAAI Press, Menlo Park, California USA 2008.
-
Arnold Baca, Martin Lames, Keith Lyons, Bernhard Nebel and Josef Wiemeyer (eds.).
Computer Science in Sport - Mission and Methods (Dagstuhl Seminar 08372).
Technical Report ,
Internationales Begegnungs- und Forschungszentrum fuer Informatik, 2008.
(Show abstract)
(Hide abstract)
(Online;DOI)
From 07.09. to 10.09., the Dagstuhl Seminar 08372 ``Computer Science in Sport - Mission and Methods'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
-
Thilo Weigel and Bernhard Nebel.
Tischfußball: Mensch versus Computer.
Informatik Spektrum 31, pp. 323-332. 2008.
(Show abstract)
(Hide abstract)
(PDF)
Table soccer is much simpler than real soccer. Nevertheless, one
faces the same challenges as in all other robotics domains. Sensors
are noisy, actions must be selected under time pressure and the
execution of actions is often less than perfect.
KiRo and StarKick are two systems that have been built to play this
game against humans. These systems are interesting because they are
the first computerized physical games that are played on a level
competitive with experienced humans. Furthermore, these systems enable
us to evaluate different AI techniques in context, e.g., action
selection methods, as is shown in the paper.
-
Diedrich Wolter, Frank Dylla, Stefan Wölfl, Jan Oliver Wallgrün, Lutz Frommberger, Bernhard Nebel and Christian Freksa.
SailAway: Spatial Cognition in Sea Navigation.
Künstliche Intelligenz 08 (1), pp. 28-30. 2008.
(Show abstract)
(Hide abstract)
(PDF)
Pedestrians, bicyclists, car drivers, boat and airplane pilots, as well as other cognitive agents participating in public traffic must respect rules in order to avoid dangerous situations and to ensure a smooth flow of traffic. The SailAway project investigates traffic and related navigational rules from a formal and computational point of view. The aim is to enable artificial cognitive agents to act in compliance with such rules. Traffic rules, which are expressed in natural language, usually subsume distinct, but similar situations and actions under more abstract spatial or temporal concepts and relations. In this paper we describe an approach to representing rules that exploits this qualitative nature of natural language descriptions used in traffic laws. Based on this approach we present methods that enable an agent to determine actions that are rule-compliant with respect to its current spatial situation. Finally we present the prototype of a control system of boats in sea navigation that implements exactly these methods.
-
Frank Dylla, Diedrich Wolter, Lutz Frommberger, Christian
Freksa, Stefan Wölfl and Bernhard Nebel.
Qualitative Methoden zur Steuerung von Agenten - SailAway:
Raumkognition zur Steuerung von Schiffen.
Industrie Management 4. 2008.
(BIB)
-
Sebastian Kupferschmid, Martin Wehrle, Bernhard Nebel and Andreas Podelski.
Faster than Uppaal?
In
A. Gupta and S. Malik (eds.),
Proceedings of the 20th International Conference on Computer Aided
Verification (CAV 2008), pp. 552-555.
Springer-Verlag 2008.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
It is probably very hard to develop a new model checker that
is faster than Uppaal for verifying correct timed automata. In
fact, our tool Mcta does not even try to compete with Uppaal
in this (i.e., Uppaal's) arena. Instead, Mcta is geared
towards analyzing incorrect specifications of timed automata.
It returns (shorter) error traces faster.
-
Dapeng Zhang, Bernhard Nebel and Armin Hornung.
Switching Attention Learning - A Paradigm for Introspection and Incremental Learning.
In
Proceedings of Fifth International Conference on Computational Intelligence, Robotics
and Autonomous Systems (CIRAS 2008), pp. 99-104.
Linz, Austria 2008.
(Show abstract)
(Hide abstract)
(PDF)
Humans improve their sport skills by eliminating one recognizable
weakness at a time. Inspired by this observation, we
define a learning paradigm in which different learners can
be plugged together. An extra attention model is in charge
of iterating over them and chosing which one to improve
next. The paradigm is named Switching Attention Learning
(SAL). The essential idea is that improving one model in the
system generates more "improvement space" for the others.
Using SAL, an application for tracking the game ball in a
table soccer game-recorder is implemented. We developed
several models and learners which work together in the SAL
framework, producing satisfying results in the experiments.
The related problems, advantages, and perspective of the
switching attention learning are discussed in this paper.
-
Anthony G. Cohn, Christian Freksa and Bernhard Nebel (eds.).
Spatial Cognition: Specialization and Integration.
Technical Report ,
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), 2007.
-
Jochen Renz and Bernhard Nebel.
Qualitative Spatial Reasoning using Constraint Calculi.
In
M. Aiello, I. Pratt-Hartmann and J. van Benthem (eds.),
Handbook of Spatial Logics, pp. 161-215.
Springer-Verlag 2007.
(Online; DOI)
-
Dapeng Zhang and Bernhard Nebel.
Recording and Segmenting Table Soccer Games -- Initial Results.
In
Proceedings of the 1st International Symposium on Skill Science 2007
(ISSS
2007), pp. 193-195.
2007.
(Show abstract)
(Hide abstract)
(PDF)
Robot KiRo can play one side of a table soccer game autonomously.
Our recent research focuses on learning from and acting against
human actions. Therefore recording and segmenting games played by
humans are motivated. In this paper, the construction of a table
soccer game recorder is sketched. An intuitive segmenting
algorithm is implemented to explore the properties of the recorded
data. A segmentation approach using Hidden Markov Models (HMMs) is
proposed.
-
Dapeng Zhang and Bernhard Nebel.
Learning a Table Soccer Robot a New Action Sequence by Observing and Imitating.
In
Proceedings of the Third Artificial Intelligence for
Interactive Digital Entertainment Conference (AIIDE
2007), pp. 61-67.
2007.
(Show abstract)
(Hide abstract)
(PDF)
Star-Kick is a commercially available and fully automatic
table soccer (foosball) robot, which plays table
soccer games against human players on a competitive
level. One of our research goals is to learn this table
soccer robot skillful actions similar to a human player
based on a moderate number of trials. Two independent
learning algorithms are employed for learning a
new lock and slide-kick action sequence by observing
the performed actions and imitating the relative actions
of a human player. The experiments with Star-Kick
show that an effective action sequence can be learned
in approximately 20 trials.
-
Diedrich Wolter, Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Bernhard Nebel and Stefan Wölfl.
Qualitative Spatial Reasoning for Rule Compliant Agent Navigation.
In
Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), pp. 673-674.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
Artificial agents participating in public traffic must respect rules that regulate traffic. Rule sets are commonly formulated in natural language using purely qualitative terms. We present a case study on how to realize rule compliant agent control in the domain of sea navigation by using qualitative spatial reasoning techniques.
-
Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Diedrich Wolter, Bernhard Nebel and Stefan Wölfl.
SailAway: Formalizing navigation rules.
In
Proceedings of the Artificial and Ambient Intelligence Symposium
on Spatial Reasoning and Communication (AISB 2007).
2007.
(Show abstract)
(Hide abstract)
(PDF)
Agents that have to solve navigational tasks need to consider
aspects that go far beyond single-agent goal-directed
deliberation: What an agent does in a specific situation often
interferes with what other agents do at the same time. In order
to avoid conflicts or even collisions, situations in space are
governed by laws, rules, and agreements between the involved
agents. For this reason, artificial agents interacting with
humans must be able to process such rule sets, which are usually
formulated in natural language. In this paper we present a case
study on how to formalize navigation rules in the domain of sea
navigation. We present an approach that uses qualitative
representations of navigation rules. Qualitative spatial
reasoning methods can be applied to distinguish permissible
actions in the set of all possible actions. We argue that an
agent’s spatial representation can be modeled on a qualitative
level in a natural way and that this also empowers sophisticated
high-level agent control.
-
Gabriele Röger and Bernhard Nebel.
Expressiveness of ADL and Golog:
Functions Make a Difference.
In
Proceedings of the 22nd AAAI Conference on Artificial
Intelligence (AAAI 2007), pp. 1051-1056.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
The main focus in the area of action languages, such as
GOLOG, was put on expressive power, while the development
in the area of action planning was focused on efficient
plan generation. An integration of GOLOG and planning languages
would provide great advantages. A user could constrain
a systems behavior on a high level using GOLOG,
while the actual low-level actions are planned by an efficient
planning system. First endeavors have been made by Eyerich
et al. by identifying a subset of the situation calculus (which
is the basis of GOLOG) with the same expressiveness as the
ADL fragment of PDDL. However, it was not proven that the
identified restrictions define a maximum subset. The most
severe restriction appears to be that functions are limited to
constants. We will show that this restriction is indeed necessary
in most cases.
-
Vittorio Ziparo, Alexander Kleiner, Bernhard Nebel and Daniele Nardi.
RFID-Based Exploration for Large Robot Teams.
In
Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2007), pp. 4606-4613.
Rome, Italy 2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To coordinate a team of robots for exploration is a challenging problem, particularly in large areas as for example the devastated area after a disaster. This problem can generally be decomposed into task assignment and multi-robot path planning. In this paper, we address both problems jointly. This is possible because we reduce significantly the size of the search space by utilizing RFID tags as coordination points.
The exploration approach consists of two parts: a stand-alone distributed local search and a global monitoring process which can be used to restart the local search in more convenient locations. Our results show that the local exploration works for large robot teams, particularly if there are limited computational resources. Experiments with the global approach showed that the number of conflicts can be reduced, and that the global coordination mechanism increases significantly the explored area.
-
Sanjiang Li and Bernhard Nebel.
Qualitative spatial representation and reasoning: A Hierarchical approach.
The Computer Journal, pp. 391-402. 2007.
(Show abstract)
(Hide abstract)
(Online; DOI)
The ability to reason in space is crucial for agents in order to make
informed decisions. Current high-level qualitative approaches to spatial
reasoning has serious decisionsciencies in not recting the hierarchical nature of spatial data and human spatial cognition. This paper proposes a
framework for hierarchical representation and reasoning about topological information, where a continuous model of space is approximated by
a collection of discrete sub-models, and spatial information is hierarchically represented in discrete sub-models in a rough set manner. The work
is based on the GRCC theory, where continuous and discrete models of
space are coped in a uni-ulmed way. Reasoning issues such as determining
the mereological (part-whole) relations between two rough regions are also
discussed. Moreover, we consider an important problem that is closely related to map generalization in cartography and Geographical Information
Science. Given a spatial considerguration at a spatialner level, we show how to construct a configuration at a coarser level while preserving the mereological
relations.
-
Jens Claßen, Patrick Eyerich, Gerhard Lakemeyer and Bernhard Nebel.
Towards an Integration of Golog and Planning.
In
Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 1846-1851.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The action language Golog has been applied successfully
to the control of robots, among other
things. Perhaps its greatest advantage is that a
user can write programs which constrain the search
for an executable plan in a xible manner. However,
when general planning is needed, Golog supports
this only in principle, but does not measure
up with state-of-the-art planners. In this paper we
propose an integration of Golog and planning in the
sense that planning problems, formulated as part of
a Golog program, are solved by a modern planner
during the execution of the program. Here we focus
on the ADL subset of the plan language PDDL.
First we show that the semantics of ADL can be
understood as progression in the situation calculus,
which underlies Golog, thus providing us with a
correct embedding of ADL within Golog. We then
show how Golog can be integrated with an existing
ADL planner for closed-world initial databases and
compare the performance of the resulting system
with the original Golog.
-
Marco Ragni, Markus Knauff and Bernhard Nebel.
A Computational Model for Spatial Reasoning with Mental Models.
In
Proceedings of the 27th Annual Cognitive Science Conference (CogSci-05).
2005.
(Show abstract)
(Hide abstract)
(PDF)
We propose a computational model for spatial reasoning by
means of mental models. Our SRM model (Spatial Reasoning
by Models) maps spatial working memory to a twodimensional
array and uses a spatial focus that places objects
in the array, manipulates the position of objects, and inspects
the array to find spatial relations that are not given in the
premises. The SRM model results in a computational
complexity measure that relies on the number of operations in
the array and the number of relations that must be handled.
The performance of the SRM model is compared to the
performance of human subjects reported in the literature and
in our own study.
-
Sylvie Thiebaux, Jörg Hoffmann and Bernhard Nebel.
In Defense of PDDL Axioms.
Artificial Intelligence 168 (1-2), pp. 38-69. 2005.
(Show abstract)
(Hide abstract)
(PDF)
There is controversy as to whether explicit support for PDDL-like axioms and derived predicates
is needed for planners to handle real-world domains effectively. Many researchers
have deplored the lack of precise semantics for such axioms, while others have argued that
it might be best to compile them away. We propose an adequate semantics for PDDL axioms
and show that they are an essential feature by proving that it is impossible to compile
them away if we restrict the growth of plans and domain descriptions to be polynomial.
These results suggest that adding a reasonable implementation to handle axioms inside the
planner is beneficial for the performance. Our experiments confirm this suggestion.
-
Thilo Weigel, Klaus Rechert and Bernhard Nebel.
Behavior Recognition and Opponent Modeling for Adaptive Table Soccer Playing.
In
U. Furbach (ed.),
KI 2005: Advances in Artificial Intelligence.
Proceedings of the 28th Annual German Conference on Artificial
Intelligence, pp. 335-350.
Springer-Verlag 2005.
(Show abstract)
(Hide abstract)
(PDF)
We present an approach for automatically adapting the behavior of an autonomous table soccer robot to a human opponent player. For this, basic actions are recognized as they are performed by the human player and charac- teristic action observations are used to establish a model of the opponent. Based on the model, the opponent’s playing skills are classified with respect to different levels of expertise and its particular offensive and defensive skills are assessed. In response to the knowledge about the opponent, the robot adapts the veloci- ties at which it attacks and defends in order to provide entertaining games for a wide range of human players with different playing skills. Experiments on two different table soccer robots validate our approach.
-
Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger, Joerg Stueckler and Bernhard Nebel.
Successful Search and Rescue in Simulated Disaster Areas.
In
Proceedings of the International RoboCup Symposium '05.
Osaka, Japan 2005.
(Show abstract)
(Hide abstract)
(PDF)
RoboCupRescue Simulation is a large-scale multi-agent simulation
of urban disasters where, in order to save lives and minimize damage, rescue
teams must effectively cooperate despite sensing and communication limitations.
This paper presents the comprehensive search and rescue approach of the ResQ
Freiburg team, the winner in the RoboCupRescue Simulation league at RoboCup
2004.
Specific contributions include the predictions of travel costs and civilian lifetime,
the efficient coordination of an active disaster space exploration, as well as
an any-time rescue sequence optimization based on a genetic algorithm.
We compare the performances of our team and others in terms of their capability
of extinguishing fires, freeing roads from debris, disaster space exploration, and
civilian rescue. The evaluation is carried out with information extracted from
simulation log files gathered during RoboCup 2004. Our results clearly explain
the success of our team, and also confirm the scientific approaches proposed in
this paper.
-
Alexander Kleiner, Bastian Steder, Christian Dornhege, Daniel Hoefler, Daniel Meyer-Delius, Johann Prediger, Joerg Stueckler, Kolja Glogowski, Markus Thurner, Matthias Luber, Michael Schnell, Rainer Kuemmerle, Timothy Burk, Tobias Braeuer and Bernhard Nebel.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
In
CDROM Proceedings of the International RoboCup Symposium '05.
Osaka, Japan 2005.
(Show abstract)
(Hide abstract)
(PDF)
This paper describes the approach of the RescueRobots Freiburg team.
RescueRobots Freiburg is a team of students from the university of Freiburg, that
originates from the former CS Freiburg team (RoboCupSoccer) and the ResQ
Freiburg team (RoboCupRescue Simulation).
Due to the high versatility of the RoboCupRescue competition we tackle the three
arenas by a a twofold approach: On the one hand we want to introduce robust
vehicles that can safely be teleoperated through rubble and building debris while
constructing three-dimensional maps of the environment. On the other hand we
want to introduce a team of autonomous robots that quickly explore a large terrain
while building a two-dimensional map. This two solutions are particularly wellsuited
for the red and yellow arena, respectively. Our solution for the orange arena
will finally be decided between these two, depending on the capabilities of both
approaches at the venue.
In this paper, we introduce some preliminary results that we achieved so far from
map building, localization, and autonomous victim identification. Furthermore
we introduce a custom made 3D Laser Range Finder (LRF) and a novel mechanism
for the active distribution of RFID tags.
1 Introduction
RescueRobots Freiburg is a team of students from the university of Freiburg. The team
originates from the former CS Freiburg team[6], which won three times the RoboCup
world championship in the RoboCupSoccer F2000 league, and the ResQ Freiburg team[2],
which won the last RoboCup world championship in the RoboCupRescue Simulation
league. The team approach proposed in this paper is based on experiences gathered at
RoboCup during the last six years.
Due to the high versatility of the RoboCupRescue competition we tackle the three
arenas by a twofold approach: On the one hand we want to introduce a vehicle that
can safely be teleoperated through rubble and building debris while constructing threedimensional
maps of the environment. On the other hand we want to introduce an autonomous
team of robots that quickly explore a large terrain while building a twodimensional
map. This two solutions are particularly well-suited for the red and yellow
arena, respectively. Our solution for the orange arena will finally be decided between
these two, depending on the capabilities of both approaches at the venue.
-
Bernhard Nebel, Thilo Weigel and Joachim Koschikowski.
Tischfußball, Hockey oder dergleichen und Verfahren zur
automatischen Ansteuerung der an Stangen angeordneten
Spielfiguren eines Tischspielgeräts für Fußball-, Hockey- oder
dergleichen.
Deutsches Patent- und Markenamt Patent DE 102 12 475. 2005.
(PDF)
-
Christian Freksa, Markus Knauff, Bernd Krieg-Brückner, Bernhard Nebel and Thomas Barkowsky (eds.).
Spatial Cognition IV.
Volume 3343 of Lecture Notes in Artificial Intelligence.
Springer-Verlag, Berlin, Heidelberg, New York 2004.
-
Alexander Scivos and Bernhard Nebel.
The Finest of Its Class: The Natural Point-Based Ternary Calculus LR for Qualitative Spatial Reasoning.
In
Spatial Cognition IV, pp. 283-303.
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(Online; DOI)
In this paper, a ternary qualitative calculus LR for spatial reasoning is presented that distinguishes between left and right. A theory is outlined for ternary point-based calculi in which all the relations are invariant when all points are mapped by rotations, scalings, or translations (RST relations). For this purpose, we develop methods to determine arbitrary transformations and compositions of RST relations. We pose two criteria which we call practical and natural. ‘Practical’ means that the relation system should be closed under transformations, compositions and intersections and have a finite base that is jointly exhaustive and pairwise disjoint. This implies that the well-known path consistency algorithm can be used to conclude implicit knowledge. ‘Natural’ calculi are close to our natural way of thinking because the base relations and their complements are connected. The main result of the paper is the identification of a maximally refined calculus amongst the practical natural RST calculi, which turns out to be very similar to Ligozat’s flip-flop calculus. From that it follows, e.g., that there is no finite refinement of the TPCC calculus by Moratz et al that is closed under transformations, composition, and intersection.
-
Thilo Weigel, Dapeng Zhang, Klaus Rechert and Bernhard Nebel.
Adaptive Vision for Playing Table Soccer.
In
S. Biundo, T. Frühwirth and G. Palm (eds.),
KI 2004: Advances in Artificial Intelligence.
Proceedings of the 27th Annual German Conference on Artificial
Intelligence, pp. 424-438.
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(PDF)
For real time object recognition and tracking often color-based methods
are used. While these methods are very ecient, they usually dependent
heavily on lighting conditions. In this paper we present a robust and ecient
vision system for the table soccer robot KiRo. By exploiting knowledge about
invariant characteristics of the table soccer game, the system is able to adapt to
changing lighting conditions dynamically and to detect relevant objects on the table
within a few milliseconds. We give experimental evidence for the robustness
and efficiency of our approach.
-
Moritz Tacke, Thilo Weigel and Bernhard Nebel.
Decision-Theoretic Planning for Playing Table Soccer.
In
S. Biundo, T. Frühwirth and G. Palm (eds.),
KI 2004: Advances in Artificial Intelligence.
Proceedings of the 27th Annual German Conference on Artificial
Intelligence, pp. 213-225.
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(PDF)
Table soccer (also called foosball) is much simpler than real soccer.
Nevertheless, one faces the same challenges as in all other robotics domains.
Sensors are noisy, actions must be selected under time pressure and the execution
of actions is often less than perfect. One approach to solve the action selection
problem in such a context is decision-theoretic planning, i.e., identifying the action
that gives the maximum expected utility. In this paper we present a decisiontheoretic
planning system suited for controlling the behavior of a table soccer
robot. The system employs forward-simulation for estimating the expected utility
of alternative action sequences. As demonstrated in experiments, this system
outperforms a purely reactive approach in simulation. However, this superiority
of the approach did not extend to the real soccer table.
-
Sebastian Trüg, Jörg Hoffmann and Bernhard Nebel.
Applying Automatic Planning Techniques to Airport
Ground-Traffic Control: A Feasibility Study.
In
S. Biundo, T. Frühwirth and G. Palm (eds.),
KI 2004: Advances in Artificial Intelligence.
Proceedings of the 27th Annual German Conference on Artificial
Intelligence, pp. 183-197.
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(PDF)
Planning techniques have matured as demonstrated by the performance of automatic planning systems at recent international competitions. Nowadays it seems feasible to apply planning systems to real-world problems. In order to get an idea of what the performance difference between special-purpose techniques and automated planning techniques is, we applied these techniques to the airport traffic control problem and compared it with a special purpose tool. In addition to a perfomance assessment, this exercise also resulted in a domain model of the airport traffic control domain. which was used as a benchmark in the 4th International Planning Competition.
-
Bernhard Nebel.
Formal Methods in Robotics.
In
Logics in Artificial Intelligence, 9th European Conference (JELIA 2004), p. 4.
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(Online; DOI)
AI research in robotics started out with the hypothesis that logical modelling and reasoning plays a key role. This assumption was seriously questioned by behaviour-based and “Nouvelle AI” approaches. The credo by this school of thinking is that explicit modelling of the environment and reasoning about it is too brittle and computationally too expensive. Instead a purely reactive approach is favoured.
-
Christian Köhler, Artur Ottlik, Hans-Hellmut Nagel and Bernhard Nebel.
Qualitative Reasoning Feeding Back into Quantitative
Model-Based Tracking.
In
Proceedings of the 16th European Conference on
Artificial Intelligence (ECAI 2004), pp. 1041-1042.
IOS Press 2004.
(Show abstract)
(Hide abstract)
(PDF)
(technical report; PDF)
Tracking vehicles in image sequences of innercity road
traffic scenes still constitutes a challenging task. Even if a-priori
knowledge about the 3D shape of vehicles, of background structure
and vehicle motion is provided, (partial) occlusion and dense vehicle
queues easily can cause initialization and tracking failures. Improving
the tracking approach requires numerous and time-consuming
experiments. Yet, these difficulties can be eased considerably by endowing
the system with a part of the qualitative knowledge, that a
human observer uses in order to judge the results. In the case reported
here, a system for qualitative reasoning has been coupled with
a quantitative model-based tracking system in order to explore the
feedback from qualitative reasoning into the geometric tracking subsystem.
-
Bernhard Nebel and Yulia Babovitch-Lierler.
When Are Behaviour Networks Well-Behaved?
In
Proceedings of the 16th European Conference on
Artificial Intelligence (ECAI 2004), pp. 672-676.
IOS Press 2004.
(Show abstract)
(Hide abstract)
(PDF)
Agents operating in the real world have to deal with a
constantly changing and only partially predictable environment and
are nevertheless expected to choose reasonable actions quickly. This
problem is addressed by a number of action-selection mechanisms.
Behaviour networks as proposed by Maes are one such mechanism,
which is quite popular. In general, it seems not possible to predict
when behaviour networks are well-behaved. However, they perform
quite well in the robotic soccer context. In this paper, we analyse the
reason for this success by identifying conditions that make behaviour
networks goal converging, i.e., force them to reach the goals regardless
of the details of the action selection scheme. In terms of STRIPS
domains one could talk of self-solving planning domains.
-
Bernd Becker, Markus Behle, Fritz Eisenbrand, Martin Fränzle, Marc Herbstritt, Christian Herde, Jörg Hoffmann, Daniel Kröning, Bernhard Nebel, Ilia Polian and Ralf Wimmer.
Bounded Model Checking and Inductive Verification of
Hybrid Discrete-continuous Systems.
In
Proceedings GI/ITG/GMM-Workshop Methoden und
Beschreibungssprachen zur Modellierung und Verifikation von
Schaltungen und Systemen, pp. 65-75.
Kaiserslautern 2004.
(Show abstract)
(Hide abstract)
(PDF)
We present a concept to signicantly advance the state of the art for bounded
model checking (BMC) and inductive verication (IV) of hybrid discrete-continuous
systems. Our approach combines the expertise of partners coming from dierent
domains, like hybrid systems modeling and digital circuit verication, bounded planning and heuristic search, combinatorial optimization and integer programming. After sketching the overall verication
ow we present rst results indicating that the
combination and tight integration of dierent verication engines is a rst step to
pave the way to fully automated BMC and IV of medium to large-scale networks of
hybrid automata.
-
Bernhard Nebel.
The Philosophical Soccer Player.
In
Proceedings of the Eights International Conference on Principles and Knowledge Representation and Reasoning (KR-02), p. 631.
2002.
-
Yannis Dimopoulos, Bernhard Nebel and Francesca Toni.
On the Computational Complexity of Assumption-based
Argumentation for Default Reasoning.
Artificial Intelligence 141 (1-2), pp. 57-78. 2002.
(Show abstract)
(Hide abstract)
(PDF)
Bondarenko et al. have recently proposed
an abstract framework for default reasoning. Besides capturing most
existing formalisms and proving that their standard semantics all
coincide, the framework extends these formalisms by generalising the
semantics of admissible and preferred arguments, originally proposed
for logic programming only. In this paper we analyse the
computational complexity of credulous and sceptical reasoning under
the semantics of admissible and preferred arguments for (the
propositional variant of) the instances of the abstract framework
capturing theorist, circumscription, logic programming, default logic,
and autoepistemic logic. Although the new semantics have been tacitly
assumed to mitigate the computational hardness of default reasoning
under the standard semantics of stable extensions, we show that in
many cases reasoning under the admissibility and preferability
semantics is computationally harder than under the standard semantics.
In particular, in the case of autoepistemic logic, sceptical reasoning
under preferred arguments is located at the fourth level of the
polynomial hierarchy, whereas the same form of reasoning under stable
extensions is located at the second level.
-
Alfonso Gerevini and Bernhard Nebel.
Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's
Interval Calculus: Computational Complexity.
In
Proceedings of the 15th European Conference on Artificial
Intelligence (ECAI'02).
2002.
(Show abstract)
(Hide abstract)
(PDF)
There exist a number of qualitative constraint calculi
that are used to
represent and reason about temporal or spatial configurations. However,
there are only very few approaches aiming to create a spatio-temporal
constraint calculus. Similar to Bennett et al., we start with the
spatial calculus RCC-8 and Allen's interval calculus in order to
construct a qualitative spatio-temporal calculus. As we will show, the basic
calculus is NP-complete, even if we only permit base relations. When
adding the restriction that the size of the spatial regions persists over
time, or that changes are continuous, the calculus becomes more useful, but
the satisfiability problem appears to be much harder. Nevertheless, we are
able to show that satisfiability is still in NP.
-
Markus Jäger and Bernhard Nebel.
Dynamic Decentralized Area Partitioning for Cooperating Cleaning Robots.
In
ICRA'02.
2002.
(Show abstract)
(Hide abstract)
(PDF)
If multiple cleaning robots are used to cooperatively clean a larger
room, e.g., an airport, the room must be partitioned among the
robots. This paper describes a dynamic and decentralized method to
partition a certain area among multiple robots. The area is divided
into polygons, which are allocated by the robots. After a robot has
allocated a certain polygon, it is responsible for cleaning the
polygon. The method described in this paper does not need any global
synchronization and does not require a global communication network.
-
Alexander Kleiner, Markus Dietl and Bernhard Nebel.
Towards a Life-Long Learning Soccer Agent.
In
Proceedings of the International RoboCup Symposium '02.
Fukuoka, Japan 2002.
(Show abstract)
(Hide abstract)
(PDF)
One problem in robotic soccer (and in robotics in general) is to adapt
skills and the overall behavior to a changing environment and to hardware
improvements. We applied hierarchical reinforcement learning in an SMDP
framework learning on all levels simultaneously. As our experiments show,
learning simultaneously on the skill level and on the skill selection level
is advantageous since it allows for a smooth adaption to a changing
environment. Furthermore, the skills we trained turn also out to be quite
competitive when run on the real robotic players of the players of our
CS Freiburg team.
-
Gerhard Lakemeyer and Bernhard Nebel (eds.).
Exploring AI in the New Millenium.
Morgan Kaufmann, San Francisco 2002.
-
Bernhard Nebel.
Helfer aus dem Stadion.
Gehirn & Geist Nr. 1/2002, pp. 6-8. 2002.
-
Bernhard Nebel.
Fußball und Künstliche Intelligenz: Vom Denken zum Handeln.
Künstliche Intelligenz Heft 1/02. 2002.
(Show abstract)
(Hide abstract)
(PDF)
Nachdem die deutsche Nationalelf sich schließlich doch noch für die Teilnahme an der Weltmeisterschaft qualifiziert hat, ist der KI-Forschergemeinde eine große Bürde abgenommen worden. Es sind jetzt nicht mehr nur die deutschen Roboterfußballspieler, die nächstes Jahr die deutsche Fußballehre im Land der aufgehenden Sonne verteidigen müssen.
Aber wie kommt es, dass sich ernsthafte Forscher mit einem Spiel wie Fußball auseinandersetzen? Wir wollen hier versuchen, eine Antwort auf diese Frage zu finden.
-
Bernhard Nebel and Alexander Scivos.
Formal Properties of Constraint Calculi for Qualitative
Spatial Reasoning.
Künstliche Intelligenz Heft 4/02, pp. 14-18. 2002.
(Show abstract)
(Hide abstract)
(PDF)
In the previous two decades, a number of qualitative constraint
calculi have been developed, which are used to represent and reason
about spatial configurations. A common property of almost all of
these calculi is that reasoning in them can be understood as solving
a binary constraint satisfaction problem over infinite domains. The
main algorithmic method that is used is constraint propagation in
the form of the path-consistency method. This approach can be
applied to a wide range of different aspects of spatial reasoning.
We describe how to make use of this representation and reasoning
technique and point out the possible problems one might encounter.
-
Thilo Weigel and Bernhard Nebel.
KiRo - An Autonomous Table Soccer Player.
In
Proceedings of the International RoboCup Symposium '02.
Fukuoka, Japan 2002.
(Show abstract)
(Hide abstract)
(PDF)
This paper presents the table soccer game as a new domain for the
research in the fields of robotics and artificial intelligence. A
system capable of playing table soccer on a competitive level and in
a fully autonomous way is described. It can serve a human both as a
teammate and an opponent but also allows for matches between two
artificial players. As the presented system can be utilized for
various purposes it is an attractive innovation for research,
education and entertainment.
-
Thilo Weigel, Jens-Steffen Gutmann, Markus Dietl, Alexander Kleiner and Bernhard Nebel.
CS Freiburg: Coordinating Robots for Successful Soccer Playing.
IEEE Transactions on Robotics and Automation 18 (5), pp. 685-699. 2002.
(Show abstract)
(Hide abstract)
(PDF)
Robotic soccer is a challenging research domain because many
different research areas have to be addressed in order to create a
successful team of robot players. This paper presents the CS
Freiburg team, the winner in the middle size league at RoboCup
1998, 2000 and 2001. The paper focuses on multi-agent coordination
for both perception and action. The contributions of this work are
new methods for tracking ball and players observed by multiple
robots, team coordination methods for strategic team formation and
dynamic role assignment, a rich set of basic skills allowing to
respond to large range of situations in an appropriate way, an
action selection method based on behavior networks as well as a
method to learn the skills and their selection. As demonstrated by
evaluations of the different methods and by the success of the team,
these methods permit the creation of a multi-robot group, which is
able to play soccer successfully. In addition, the developed methods
promise to advance the state of the art in the multi-robot field.
-
Wolfgang Hatzack and Bernhard Nebel.
Solving the Operational Traffic Control Problem.
In
A. Cesta and D. Borrajo (eds.),
Proceedings of the 6th European Conference on Planning
(ECP 2001).
2001.
(Show abstract)
(Hide abstract)
(PDF)
The operational traffic control problem comes up in a number of different
contexts. It involves the coordinated movement of a set of vehicles and has
by and large the flavor of a scheduling problem. In trying to apply
scheduling techniques to the problem, one notes that this is a job-shop
scheduling problem with blocking, a type of scheduling problem that is quite
unusual. In particular, we will highlight a condition necessary to
guarantee that job-shop schedules can be executed in the presences of the
blocking constraint. Based on the insight that the traffic problem is a
scheduling problem, we can derive the computational complexity of the
operational traffic control problem and can design some algorithms to deal
with this problem. In particular, we will specify a very simple method that
works well in fast-time simulation contexts.
-
Jörg Hoffmann and Bernhard Nebel.
RIFO revisited: Detecting Relaxed Irrelevance.
In
A. Cesta and D. Borrajo (eds.),
Proceedings of the 6th European Conference on Planning
(ECP 2001).
2001.
(Show abstract)
(Hide abstract)
(PDF)
RIFO, as has been proposed by Nebel et al., is a method
that can automatically detect irrelevant information in planning tasks. The
idea is to remove such irrelevant information as a preprocess to planning.
While RIFO has been shown to be useful in a number of domains, its main
disadvantage is that it is not completeness preserving. Furthermore, the
preprocess often takes more running time than nowadays stateoftheart
planners, like FF, need for solving the entire planning task.
We introduce the notion of relaxed irrelevance, concerning actions which are
never needed within the relaxation that heuristic planners like FF and HSP
use for computing their heuristic values. The idea is to speed up the heuris
tic functions by reducing the action sets considered within the relaxation.
Starting from a sufficient condition for relaxed irrelevance, we introduce
two preprocessing methods for filtering action sets. The first preprocessing
method is proven to be completenesspreserving, and is empirically shown to
terminate fast on most of our testing examples. The second method is fast on
all our testing examples, and is empirically safe. Both methods have drastic
pruning impacts in some domains, speeding up FF's heuristic function, and
in effect the planning process.
-
Reinhard Moratz and Bernhard Nebel.
Sichtweisen der kognitiven Robotik.
Künstliche Intelligenz 15 (3), p. 71. 2001.
-
Markus Dietl, Jens-Steffen Gutmann and Bernhard Nebel.
Cooperative Sensing in Dynamic Environments.
In
Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS-2001).
2001.
(Show abstract)
(Hide abstract)
(PDF)
This work presents methods for tracking
objects from noisy and unreliable data taken by a team of robots. We
develop a multiobject tracking algorithm based on Kalman filtering
and a singleobject tracking method involving a combination of Kalman
filtering and Markov localization for outlier detection. We apply
these methods in the context of robot soccer for robots participating
in the middlesize league and compare them to a simple averaging
method. Results including situations from real competition games are
presented.
-
Markus Dietl, Jens-Steffen Gutmann and Bernhard Nebel.
CS Freiburg: Global View by Cooperative Sensing.
In
International RoboCup Symposium 2001.
2001.
(Show abstract)
(Hide abstract)
(PDF)
Global vision systems as found in the small size league are prohibited
in the middle size league. This paper presents methods for creating a
global view of the world by cooperative sensing of a team of
robots. We develop a multiobject tracking algorithm based on Kalman
filtering and a singleobject tracking method involving a combination
of Kalman filtering and Markov localization for outlier detection. We
apply these methods for robots participating in the middlesize league
and compare them to a simple averaging method. Results including
situations from real competition games are presented.
-
Jens-Steffen Gutmann, Thilo Weigel and Bernhard Nebel.
A Fast, Accurate, and Robust Method for Self-Localization in
Polygonal Environments Using Laser-Range-Finders.
Advanced Robotics 14 (8), pp. 651-668. 2001.
(Show abstract)
(Hide abstract)
(PDF)
Self-localization is important in almost all robotic tasks. For playing an
aesthetic and effective game of robotic soccer, self-localization is a
necessary prerequisite. When we designed our robotic soccer team for
participating in robotic soccer competitions, it turned out that all
existing approaches did not meet our requirements of being fast, accurate,
and robust. For this reason, we developed a new method, which is presented
and analyzed in this paper. This method is one of the key components and is
probably one of the explanations for the success of our team in national and
international competitions. We present also experimental evidence that our
method outperforms other self-localization methods in the RoboCup
environment.
-
Jörg Hoffmann and Bernhard Nebel.
The FF Planning System: Fast Plan Generation Through
Heuristic Search.
Journal of Artificial Intelligence Research 14, pp. 253-302. 2001.
(Show abstract)
(Hide abstract)
(PDF)
We describe and evaluate the algorithmic techniques that are used in
the FF planning system. Like the HSP system, FF relies on forward
state space search, using a heuristic that estimates goal
distances by ignoring delete lists. Unlike HSP's heuristic, our
method does not assume facts to be independent. We introduce a
novel search strategy that combines hill-climbing with systematic
search, and we show how other powerful heuristic information can
be extracted and used to prune the search space. FF was the most
successful automatic planner at the recent AIPS-2000 planning
competition. We review the results of the competition, give data
for other benchmark domains, and investigate the reasons for the
runtime performance of FF compared to HSP.
-
Jörg Hoffmann and Bernhard Nebel.
What makes the difference between HSP and FF?
In
IJCAI Workshop on Empirical AI.
Seattle 2001.
(Show abstract)
(Hide abstract)
(PDF)
The HSP and FF systems are state-of-the-art domain independent planners. FF can historically be seen as a successor of HSP. It is based on the same ideas like HSP, but differs from its predecessor in a number of details. FF outperforms HSP in many planning domains. We have carried out a large scale experiment where we ran all configurations of FF's new techniques on a sizeable set of planning tasks. We describe the experimental design, and present our findings. The results give a clear picture of what the most important reasons are for FF's performance advantage over HSP.
-
Jörg Hoffmann and Bernhard Nebel.
Towards Thorough Empirical Methods for AI Planning.
In
IJCAI Workshop on Empirical AI.
Seattle 2001.
(Show abstract)
(Hide abstract)
(PDF)
Empirical investigations in the area of AI planning have been focused on a comparatively small set of benchmark tasks. Trying to design larger scale experiments for well-founded empirical reasoning in that area, one encounters a number of severe problems. While some of these problems are inherent to the field, others have plainly been ignored. In our own work, we have made some first steps towards addressing these problems.
-
Guido Isekenmeier, Bernhard Nebel and Thilo Weigel.
Evaluation of the Performance of CS Freiburg 1999 and CS
Freiburg 2000.
In
International RoboCup Symposium 2001.
2001.
(Show abstract)
(Hide abstract)
(PDF)
One of the questions one may ask when following research in robotic soccer
is whether there is a measurable progress over the years in the robotic
leagues. While everybody who has followed the games from 1997 to 2000 would
agree that the robotic soccer players in the F2000 league have improved
their playing skills, there is no hard evidence to justify this opinion. We
tried to identify a number of criteria that measure the ability to play
robotic soccer and analyzed all the games CS Freiburg played at RoboCup 1999
and 2000. As it turns out, for almost all criteria, there is a statistically
significant increase for CS Freiburg and the opponent teams
demonstrating that the level of play has indeed increased from 1999
to 2000.
-
Markus Jäger and Bernhard Nebel.
Decentralized Collision Avoidance, Deadlock Detection, and
Deadlock Resolution for Multiple Mobile Robots.
In
Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS-2001).
2001.
(Show abstract)
(Hide abstract)
(PDF)
This paper describes a method for coordinating the independently
planned trajectories of multiple mobile robots to avoid collisions and
deadlocks among them. Whenever the distance between two robots drops
be low a certain value, they exchange information about their planned
trajectories and determine whether they are in danger of a
collision. If a possible collision is detected, they monitor their
movements and, if necessary, insert idle times between certain
segments of their trajectories in or der to avoid the collision.
Deadlocks among two or more robots occur if a number of robots block
each other in a way such that none of them is able to continue along
its trajectory without causing a collision. These deadlocks are
reliably detected. After a deadlock is detected, the trajectory
planners of each of the involved robots are successively asked to plan
an alternative trajectory until the deadlock is resolved. We use a
combination of three fully distributed algo rithms to reliably solve
the task. They do not use any global synchronization and do not
interfere with each other.
-
Bernhard Nebel (ed.).
Seventeenth International Joint Conference on Artificial
Intelligence (IJCAI 2001).
Morgan Kaufmann, Seattle, Washington, USA 2001.
-
Bernhard Nebel.
Cooperating Physical Robots: A Lesson in Playing Robotic
Soccer.
In
M. Luck, V. Marik, O. Stepankova and R. Trappl (eds.),
Multi-Agent Systems and Applications, pp. 404-414.
Springer-Verlag 2001.
(Show abstract)
(Hide abstract)
(PDF)
Having a robot that carries out a task for you is certainly of some help.
Having a group of robots seems to be even better because in this case the
task may be finished faster and more reliably. However, dealing with a
group of robots can make some problems more difficult. In this paper we
sketch some of the advantages and some problems that come up when
dealing with groups of robots. In particular, we describe techniques
as they have been developed and tested in the area of robotic soccer.
-
Bernhard Nebel.
Ranking? Publikationen, Zitate, Drittmittelprojekte und Promotionen an
deutschen Informatikfakultäten im Spiegel des WWW.
Informatik-Spektrum 24 (4), pp. 234-249. 2001.
(Show abstract)
(Hide abstract)
(PDF)
Will man etwas über die wissenschaftliche
Produktivität einer Fakultät in Erfahrung bringen, kann man
Indikatoren wie Anzahl von Publikationen, aktuelle Veröffentlichungen
in internationalen Fachzeitschriften, Anzahl von Zitaten, Anzahl von
Promotionen und Anzahl und Umfang von Drittmittelprojekten versuchen
zu bestimmen. Mittlerweile ist im World Wide Web so viel
Information vorhanden, dass die Bestimmung dieser Indikatoren keinen
großen Aufwand erfordert und problemlos nachvollziehbar ist. In diesem
Artikel werden die Resultate einer Auswertung zur Bestimmung der
Indikatoren für die deutschen Informatik-Fakultäten, -Fachbereiche und
-Institute beschrieben, die auf im WWW frei zugänglichen Quellen
beruht.
-
Bernhard Nebel.
Logics for Knowledge Representation.
In
N. J. Smelser and P. B. Baltes (eds.),
International Encyclopedia of the Social and Behavioral
Sciences.
Kluwer, Dordrecht 2001.
(Show abstract)
(Hide abstract)
(PDF)
Knowledge representation and reasoning plays a central role in
Artificial Intelligence, and formal logic has become the prevalent
formal tool in this area. We give a brief historical sketch of the
development of the field and describe what interesting developments
the last two decades have brought in terms of new logical
formalisms. In particular, we argue that the important point about
using logic is not so much which particular logic used, but that the
logic method is used to understand knowledge and reasoning.
-
Jochen Renz and Bernhard Nebel.
Efficient Methods for Qualitative Spatial Reasoning.
Journal of Artificial Intelligence Research 15, pp. 289-318. 2001.
(Show abstract)
(Hide abstract)
(PDF)
The theoretical properties of qualitative spatial reasoning in the
RCC-8 framework have been analyzed extensively. However, no empirical
investigation has been made yet. Our experiments show that the
adaption of the algorithms used for qualitative temporal reasoning can
solve large RCC-8 instances, even if they are in the phase transition
region -- provided that one uses the maximal tractable subsets of RCC-8
that have been identified by us. In particular, we demonstrate that
the orthogonal combination of heuristic methods is successful in
solving almost all apparently hard instances in the phase transition
region up to a certain size in reasonable time.
-
Alexander Scivos and Bernhard Nebel.
Double-Crossing: Decidability and Computational Complexity of
a Qualitative Calculus for Navigation.
In
Proc. COSIT-2001.
Springer-Verlag 2001.
(Show abstract)
(Hide abstract)
(PDF)
The Double Cross calculus has been proposed for the purpose of
navigation based on qualitative information about spatial configurations.
Up until now, however, no results about algorithmic properties of this
calculus are known. First, we explore the possibility of applying constraint
propagation techniques to solve the reasoning problem in this calculus. For
this purpose, we have to generalize the known techniques for binary
relations because the Double Cross calculus is based on ternary relations.
We will show, however, that such a generalization leads to problems. The
Double Cross calculus is not closed under composition and permutation.
Further, as we will show, there exists no finite refinement of the base
relations with such a closure property. Finally, we show that determining
satisfiability of constraint systems over Double Cross relations is NP-hard,
even if only the base relations of the Double Cross calculus are used. On
the positive side, however, we show that the reasoning problem is solvable
in PSPACE.
-
Thilo Weigel, Willi Auerbach, Markus Dietl, Burkhard Dümler, Jens-Steffen Gutmann, Kornel Marko, Klaus Müller, Bernhard Nebel, Boris Szerbakowski and Maximilian Thiel.
CS Freiburg: Doing the Right Thing in a Group.
In
P. Stone, G. Kraetzschmar and T. Balch (eds.),
RoboCup 2000: Robot Soccer World Cup IV, pp. 52-63.
Springer-Verlag 2001.
(Show abstract)
(Hide abstract)
(PDF)
The success of CS Freiburg at RoboCup 2000 can be attributed to an
effective cooperation between players based on sophisticated soccer
skills and a robust and accurate self-localization method. In this
paper, we present our multi-agent coordination approach for both,
action and perception, and our rich set of basic skills which allow
to respond to a large range of situations in an appropriate way.
Furthermore our action selection method based on an extension to
behavior networks is described. Results including statistics from CS
Freiburg final games at RoboCup 2000 are presented.
-
Thilo Weigel, Alexander Kleiner, Florian Diesch, Markus Dietl, Jens-Steffen Gutmann, Bernhard Nebel, Patrick Stiegeler and Boris Szerbakowski.
CS Freiburg 2001.
In
International RoboCup Symposium 2001.
2001.
(Show abstract)
(Hide abstract)
(PDF)
The CS Freiburg team has become F2000 champion the third time in the
history of RoboCup. The success of our team can probably be
attributed to its robust sensor interpretation and its team play. In
this paper, we will focus on new developments in our vision system,
in our path planner, and in the cooperation component.
-
Thilo Weigel, Jens-Steffen Gutmann, Bernhard Nebel, Klaus Müller and Markus Dietl.
CS Freiburg: Sophisticated Skills and Effective Cooperation.
In
Proc. European Control Conference (ECC-01).
Porto, Portugal 2001.
(Show abstract)
(Hide abstract)
(PDF)
The success of CS Freiburg at RoboCup 2000 can be attributed
to a robust and accurate perception approach and an effec
tive cooperation between players based on sophisticated soc
cer skills. In this paper, we present our multiagent coordi
nation approach for both, action and perception, and our rich
set of basic skills which allow to respond to a large range of
situations in an appropriate way. Furthermore, our action se
lection method based on an extension to behavior networks is
described. Results including statistics from CS Freiburg final
games at RoboCup 2000 are presented.
-
Jens-Steffen Gutmann, Thilo Weigel and Bernhard Nebel.
Fast, Accurate, and Robust Self-Localization in the RoboCup Environment.
In
Manuela M. Veloso, Enrico Pagello and Hiroaki Kitano (eds.),
RoboCup-99: Robot Soccer World Cup III, pp. 304-317.
Springer 2000.
(Show abstract)
(Hide abstract)
(Online;DOI)
Self-localization is important in almost all robotic tasks. For playing an aesthetic and effective game of robotic soccer, self-localization is a necessary prerequisite. When we designed our robotic soccer team for RoboCup’98, it turned out that all existing approaches did not meet our requirements of being fast, accurate, and robust. For this reason, we developed a new method, which is presented and analyzed in this paper. We additionally present experimental evidence that our method outperforms other methods in the RoboCup environment.
-
Yannis Dimopoulos, Bernhard Nebel and Francesca Toni.
Finding Admissible and Preferred Arguments Can be Very
Hard.
In
Principles of Knowledge Representation and Reasoning,
Proceedings of the 7th International Conference
(KR'2000).
2000.
(Show abstract)
(Hide abstract)
(PDF)
Bondarenko et al. have recently proposed an extension of the
argumentation-theoretic semantics of admissible and
preferred arguments, originally proposed for logic programming only,
to a number of other nonmonotonic reasoning formalisms. In this paper
we analyse the computational complexity of credulous and
sceptical reasoning under the semantics of admissible and preferred
arguments for (the propositional variant of) some well-known
frameworks for nonmonotonic reasoning, i.e. Theorist, Circumscription
and Autoepistemic Logic. While the new semantics have been assumed to
mitigate the computational problems of nonmonotonic reasoning under
the standard semantics of stable extensions, we show that in
many cases reasoning under the new semantics is computationally harder
than under the standard semantics. In particular, for Autoepistemic
Logic, the sceptical reasoning problem under the semantics of
preferred arguments is located at the fourth level of the polynomial
hierarchy, two levels above the same problem under the standard
semantics. In some cases, however, reasoning under the new semantics
becomes easier - reducing to reasoning in the monotonic logics
underlying the nonmonotonic frameworks.
-
Jens-Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor and Thilo Weigel.
The CS Freiburg Team: Playing Robotic Soccer Based on an
Explicit World Model.
AI Magazine 21 (1), pp. 37-46. 2000.
(Show abstract)
(Hide abstract)
(preliminary version; PDF)
Robotic soccer is an ideal task to demonstrate new techniques and to explore
new problems. Moreover, problems and solutions can be easily communicated
because soccer is a well-known game. Our intention in building a robotic
soccer team and participating in RoboCup'98 was, first of all, to
demonstrate the usefulness of the self-localization methods we have
developed. Secondly, we wanted to show that playing soccer based on an
explicit world model is much more effective than other methods. Thirdly, 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 on the first two points. Moreover, robotic soccer gave us
the opportunity to study problems in distributed, cooperative sensing.
-
Jens-Steffen Gutmann, Bernhard Nebel and Christian Reetz.
CS Freiburg: Architektur und Aktionsauswahl im
Roboterfuball.
In
Proc. AMS-2000.
2000.
(Show abstract)
(Hide abstract)
(PDF)
Roboterfußball ist ein wissenschaftliches
anspruchsvolles Forschungsproblem, das erfordert, Probleme aus den
Bereichen Robotik, Künstliche Intelligenz und Multi-Agenten-Systeme zu
lösen und die Lösungen in einem System zu integrieren, um ein
erfolgreiches Roboterfußballteam zu kreieren. In diesem Papier
beschreiben wir die Schlüsselkomponenten des CS Freiburg
Teams. Dabei fokussieren wir auf die Selbstlokalisation und
Objekterkennungsmethoden und die Integration aller Information in ein
globales Weltmodell. Basierend auf diesem Weltmodell werden dann
Aktionsselektion, Pfadplanung und Kooperation realisiert. Das
resultierende System ist äußerst erfolgreich und hat bisher lediglich
ein Spiel in einem Wettbewerb verloren.
-
Bernhard Nebel.
On the Compilability and Expressive Power of Propositional
Planning Formalisms.
Journal of Artificial Intelligence Research 12, pp. 271-315. 2000.
(Show abstract)
(Hide abstract)
(PDF)
The recent approaches of extending the GRAPHPLAN algorithm to handle more
expressive planning formalisms raise the question of what the formal meaning
of ``expressive power'' is. We formalize the intuition that expressive power
is a measure of how concisely planning domains and plans can be expressed in
a particular formalism by introducing the notion of ``compilation schemes''
between planning formalisms. Using this notion, we analyze the
expressiveness of a large family of propositional planning formalisms,
ranging from basic STRIPS to a formalism with conditional effects,
partial state specifications, and propositional formulae in the
preconditions. One of the results is that conditional effects cannot be
compiled away if plan size should grow only linearly but can be compiled
away if we allow for polynomial growth of the resulting plans. This result
confirms that the recently proposed extensions to the GRAPHPLAN algorithm
concerning conditional effects are optimal with respect to the
``compilability'' framework. Another result is that general propositional
formulae cannot be compiled into conditional effects if the plan size should
be preserved linearly. This implies that allowing general propositional
formulae in preconditions and effect conditions adds another level of
difficulty in generating a plan.
-
Bernhard Nebel.
On the Expressive Power of Planning Formalisms: Conditional
Effects and Boolean Preconditions in the STRIPS Formalism.
In
J. Minker (ed.),
Logic-Based Artificial Intelligence, pp. 469-490.
Kluwer, Dordrecht 2000.
(Show abstract)
(Hide abstract)
(PDF)
The notion of ``expressive power'' is often used in the literature on
planning. However, it is usually only used in an informal way. In this
paper, we will formalize this notion using the ``compilability framework''
and analyze the expressive power of some variants of STRIPS allowing for
conditional effects and arbitrary Boolean formulae in preconditions. One
interesting consequence of this analysis is that we are able to confirm a
conjecture by Bäckström that preconditions in conjunctive normal form
add to the expressive power of propositional STRIPS. Further, we will show
that STRIPS with conditional effects is incomparable to STRIPS with
Boolean formulae as preconditions. Finally, we show that preconditions in
conjunctive normal form do not add any expressive power once we have
conditional effects.
-
Bernhard Nebel.
Knowledge Representation and Reasoning - The Theoretical Side of AI.
In
14th European Conference on Artificial Intelligence,
Proceedings (ECAI 2000), p. 763.
Berlin, Germany 2000.
(Show abstract)
(Hide abstract)
(PDF)
Representing knowledge and reasoning with it is at the heart of most AI
systems. Nevertheless, the field of Knowledge Representation and Reasoning
(KR&R) does not seem to have much impact on practical work in AI. I will
try to point out the reasons for the discrepancy and I will argue that KR&R
can be understood as Theoretical Artifical Intelligence. Further, I point
out a number of fruitful applications of KR&R techniques.
-
Bernhard Nebel and Thilo Weigel.
The CS Freiburg 2000 Team.
In
Fourth International Workshop on RoboCup.
Melbourne, Australia 2000.
(PDF)
-
Yannis Dimopoulos, Bernhard Nebel and Francesca Toni.
Preferred Arguments are Harder to Compute than Stable
Extensions.
In
Proceedings of the 16th International Joint Conference on
Artificial Intelligence (IJCAI 1999).
Stockholm, Sweden 1999.
(Show abstract)
(Hide abstract)
(PDF)
Based on an abstract framework for nonmonotonic reasoning, Bondarenko et
al. have extended the logic programming semantics of admissible
and preferred arguments to other nonmonotonic formalisms such as
circumscription, auto-epistemic logic and default logic. Although the new
semantics have been tacitly assumed to mitigate the computational problems
of nonmonotonic reasoning under the standard semantics of stable
extensions, it seems questionable whether they improve
the worst-case behaviour. As a matter of fact, we show that credulous
reasoning under the new semantics in propositional logic programming
and propositional default logic has the same computational
complexity as under the standard semantics. Furthermore, sceptical
reasoning under the admissibility semantics is easier -
since it is trivialised to monotonic reasoning. Finally,
sceptical reasoning under the preferability semantics is
harder than under the standard semantics.
-
Jens-Steffen Gutmann, Thilo Weigel and Bernhard Nebel.
Fast, Accurate, and Robust Self-Localization in Polygonal
Environments.
In
Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS '99).
Kyongju, Korea 1999.
(Show abstract)
(Hide abstract)
(preliminary version; PDF)
Self-localization is important in almost all robotic tasks. For playing an
aesthetic and effective game of robotic soccer, self-localization is a
necessary prerequisite. When we designed our robotic soccer team for
RoboCup'98, it turned out that all existing approaches did not meet our
requirements of being fast, accurate, and robust. For this reason, we
developed a new method, which is presented and analyzed in this paper. We
additionally present experimental evidence that our method outperforms
other methods in the RoboCup environment.
-
Jens-Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor, Thilo Weigel and Bruno Welsch.
The CS Freiburg Robotic Soccer Team: Reliable
Self-Localization, Multirobot Sensor Integration, and Basic Soccer
Skills.
In
M. Asada (ed.),
RoboCup-98: Robot Soccer World Cup II, pp. 93-108.
Springer-Verlag, Berlin, Heidelberg, New York 1999.
(Show abstract)
(Hide abstract)
(PDF)
Robotic soccer is a challenging research domain because problems in
robotics, artificial intelligence, multi-agent systems and real-time
reasoning have to be solved in order to create a successful team of
robotic soccer players. In this paper, we describe the key
components of the CS Freiburg team. We focus on the
self-localization and object recognition method based on using laser
range finders and the integration of all this information into a
global world model. Using the explicit model of the environment
built by these components, we have implemented path planning, simple
ball handling skills and basic multi-agent cooperation. The
resulting system is a very successful robotic soccer team, which has
not lost any game yet.
-
Jens-Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor and Thilo Weigel.
Reliable Self-Localization, Multirobot Sensor Integration,
Accurate Path-Planning and Basic Soccer Skills: Playing an
Effective Game of Robotic Soccer.
In
Nineth International Conference on Advanced Robotics
(ICAR 1999).
1999.
(Show abstract)
(Hide abstract)
(PDF)
Robotic soccer is a challenging research domain because problems in
robotics, artificial intelligence, multi-agent systems and real-time
reasoning have to be solved in order to create a successful team of
robotic soccer players. In this paper, we describe the key
components of the CS Freiburg team. We focus on the
self-localization and object recognition method based on using laser
range finders and the integration of all this information into a
global world model. Using the explicit model of the environment
built by these components, we have implemented path planning, simple
ball handling skills and basic multi-agent cooperation. The
resulting system is a very successful robotic soccer team, which has
not lost any official game yet.
-
Bernhard Nebel.
Compilation Schemes: A Theoretical Tool for Assessing the
Expressive Power of Planning Formalisms.
In
KI-99: Advances in Artificial Intelligence.
Springer-Verlag, Bonn 1999.
(Show abstract)
(Hide abstract)
(PDF)
The recent approaches of extending the GRAPHPLAN algorithm to handle more
expressive planning formalisms raise the question of what the formal meaning
of ``expressive power'' is. We formalize the intuition that expressive power
is a measure of how concisely planning domains and plans can be expressed in
a particular formalism by introducing the notion of ``compilation schemes''
between planning formalisms. Using this notion, we analyze the expressive
power of a large family of propositional planning formalisms and show, e.g.,
that Gazen and Knoblock's approach to compiling conditional
effects away is optimal.
-
Bernhard Nebel.
What is the Expressive Power of Disjunctive
Preconditions?
In
Proceedings of the 5th European Conference on Planning
(ECP 1999).
1999.
(Show abstract)
(Hide abstract)
(PDF)
While there seems to be a general consensus about the expressive power of a
number of language features in planning formalisms, one can find many
different statements about the expressive power of disjunctive
preconditions. Using the ``compilability framework,'' we show that
preconditions in conjunctive normal form add to the expressive power of
propositional STRIPS, which confirms a conjecture by Bäckström.
Further, we show that preconditions in conjunctive
normal form do not add any expressive power once we have conditional
effects.
-
Bernhard Nebel.
Die Ausdrucksstärke von Planungsformalismen: Eine formale
Charakterisierung.
Künstliche Intelligenz Heft 3/99, pp. 12-19. 1999.
(Show abstract)
(Hide abstract)
(preliminary version; PDF)
Die Ausdrucksstärke von Planungsformalismen wird in vielen Arbeiten im
Gebiet der Handlungsplanung thematisiert, ohne daß der Begriff jedoch
formal fundiert wird. Insbesondere im Kontext des von Blum und Furst
entwickeltem Graphplan-Algorithmus gewinnt dieses Thema Relevanz, da viele
Forschungsarbeiten sich mit dem Problem auseinandersetzen, ob und wie der
Graphplan-Algorithmus erweitert werden kann, um ausdrucksstarke Formalismen
zu behandeln. In diesem Papier wird eine Methode zur Messung der relativen
Ausdrucksstä;rke von Planungsformalismen vorgestellt, das auf Ideen aus dem
Gebiet der Wissenskompilation beruht. Die Intuition ist dabei, daß ein
Formalismus so mächtig wie ein zweiter Formalismus ist, falls sich alle
Domänenbeschreibungen des zweiten Formalismus "einfach" innerhalb des
ersten Formalismus ausdrücken lassen und die resultierenden Pl"ane nicht zu
stark aufgebläht werden. Diese intuitive Charakterisierung der relativen
Ausdrucksstärke wird mit Hilfe von sogenannten "Kompilationsschemata"
formalisiert, und darauf aufbauend werden propositionale Planungsformalismen
entsprechend ihrer Ausdrucksstärke klassifiziert.
-
Bernhard Nebel, Jens-Steffen Gutmann and Wolfgang Hatzack.
The CS Freiburg '99 Team.
In
Third International Workshop on RoboCup.
1999.
(Show abstract)
(Hide abstract)
(PDF)
Based on the design of the CS Freiburg team, which participated successfully
in Robocup'98, we developed a new team of robotic soccer players. While the
hardware components and software architecture remained mainly unchanged, we
invested some effort to improve the sensor data gathering and
interpretation, the tactical components and the behavior-based control
module. The main goal is to enable the players to act in a truly cooperative
style which leads, for instance, to passing the ball from one player to
another.
-
Jochen Renz and Bernhard Nebel.
On the Complexity of Qualitative Spatial Reasoning: A Maximal
Tractable Fragment of the Region Connection Calculus.
Artificial Intelligence 108 (1-2), pp. 95-149. 1999.
(Show abstract)
(Hide abstract)
(PDF)
The computational properties of qualitative spatial reasoning have been
investigated to some degree. However, the question for the boundary between
polynomial and NP-hard reasoning problems has not been addressed yet. In
this paper we explore this boundary in the ``Region Connection Calculus''
RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on
this encoding, we prove that reasoning is NP-complete in general and
identify a maximal tractable subset of the relations in RCC-8 that
contains all base relations. Further, we show that for this subset
path-consistency is sufficient for deciding consistency.
-
Bernhard Nebel.
Frame-Based Systems.
In
R. A. Wilson and F Keil (eds.),
MIT Encyclopedia of the
Cognitive Sciences, pp. 324-325.
MIT Press, Cambridge, MA 1999.
-
Ulrich Furbach, Hans-Jürgen Bürckert, Joachim Hertzberg, Bernhard Nebel, Gerhard Brewka, Gerhard Lakemeyer, Torsten Schaub and Frank Puppe.
Ist die Wissensrepräsentation tot?
Künstliche Intelligenz 9 (5), pp. 18-26. 1995.
-
Bernhard Nebel and Hans-Jürgen Bürckert.
Reasoning about Temporal Relations: A Maximal Tractable
Subclass of Allen's Interval Algebra.
Journal of the ACM 42, pp. 43-66. 1995.
(Show abstract)
(Hide abstract)
(PDF)
(TAR.GZ)
We introduce a new subclass of Allen's interval algebra we call
``ORD-Horn subclass,'' which is a strict superset of the
``pointisable subclass.'' We prove that reasoning in the
ORD-Horn subclass is a polynomial-time problem and show that the
path-consistency method is sufficient for deciding
satisfiability. Further, using an extensive machine-generated
case analysis, we show that the ORD-Horn subclass is a maximal
tractable subclass of the full algebra (assuming P=/=NP). In
fact, it is the unique greatest tractable subclass amongst the
subclasses that contain all basic relations.
-
Bernhard Nebel and Jana Koehler.
Plan Reuse versus Plan Generation: A Theoretical and Empirical
Analysis.
Artificial Intelligence 76, pp. 427-454. 1995.
(Show abstract)
(Hide abstract)
(PDF)
The ability of a planner to reuse parts of old plans is
hypothesized to be a valuable tool for improving efficiency of
planning by avoiding the repetition of the same planning effort.
We test this hypothesis from an analytical and empirical point
of view. A comparative worst-case complexity analysis of
generation and reuse under different assumptions reveals that it
is not possible to achieve a provable efficiency gain of reuse
over generation. Further, assuming ``conservative'' plan
modification, plan reuse can actually be strictly more difficult
than plan generation. While these results do not imply that
there won't be an efficiency gain in some situations, retrieval
of a good plan may present a serious bottleneck for plan reuse
systems, as we will show. Finally, we present the results of an
empirical study of two different plan reuse systems, pointing
out possible pitfalls one should be aware of when attempting to
employ reuse methods.
-
Christer Bäckström and Bernhard Nebel.
Complexity Results for SAS+ Planning.
Computational Intelligence 11, pp. 625-655. 1995.
(Show abstract)
(Hide abstract)
(PDF)
We have previously reported a number of tractable planning problems
defined in the SAS+ formalism. This paper complements these results
by providing a complete map over the complexity of SAS+ planning under
all combinations of the previously considered restrictions. We
analyze the complexity both of finding a minimal plan and of finding
any plan. In contrast to other complexity surveys of planning we
study not only the complexity of the decision problems but also of the
generation problems. We prove that the SAS+-PUS problem is the
maximal tractable problem under the restrictions we have considered if
we want to generate minimal plans. If we are satisfied with any plan,
then we can generalize further to the SAS+-US problem, which we prove
to be the maximal tractable problem in this case.
-
Bernhard Nebel.
Komplexitätsanalysen in der Künstlichen Intelligenz.
Künstliche Intelligenz 2/95, pp. 6-14. 1995.
(Show abstract)
(Hide abstract)
(PDF)
Die Analyse der Berechenbarkeitskomplexität von typischen KI-Problemen
sowie der Entwurf effizienter Verfahren zum Lösen dieser Probleme
hat in den letzten Jahren verstärkt Interesse gefunden.
In diesem Beitrag wollen wir auf den Sinn von Komplexitätsanalysen eingehen,
examplarisch das Vorgehen bei solchen Analysen darstellen und einige
Methoden zum Umgang mit dem Komplexitätsproblem skizzieren.
-
Bernhard Nebel.
Computational Properties of Qualitative Spatial Reasoning:
First Results.
In
KI-95: Advances in Artificial Intelligence, pp. 233-244.
Springer-Verlag, Bielefeld, Germany 1995.
(Show abstract)
(Hide abstract)
(PDF)
While the computational properties of qualitative temporal reasoning
have been analyzed quite thoroughly, the computational properties of
qualitative spatial reasoning are not very well investigated. In fact,
almost no completeness results are known for qualitative spatial
calculi and no computational complexity analysis has been carried out
yet. In this paper, we will focus on the so-called RCC approach and
use Bennett's encoding of spatial reasoning in intuitionistic logic in
order to show that consistency checking for the topological base
relations can be done efficiently. Further, we show that path-consistency
is sufficient for deciding global consistency. As a side-effect we
prove a particular fragment of propositional intuitionistic logic to
be tractable.
-
Alex Borgida, Maurizio Lenzerini, Daniele Nardi and Bernhard Nebel (eds.).
Proceedings of the International Workshop on Description Logics.
Technical Report 07.95,
Universita degli Studi di Roma "La Sapienza", Dipartimento di Informatica e Sistemica, Roma, Italy, 1995.
(Show abstract)
(Hide abstract)
(PDF)
This volume contains the collection of papers that were presented at
the 1995 International Workshop on Description Logics that was held on
June 2 and 3, 1995 at the Centro Congressi of Universita di Roma "La
Sapienza", Italy. The Workshop was organized in 8 sessions, with 3
sessions including contributions on theoretical issues about
Description Logics: "Extensions to Description Logics," "Integration
with other formalisms," and "Foundations," and 3 sessions on the
development of knowledge representation systems based on Description
Logics: "Connections to Databases," "Applications," and "Systems." The
remaining two sessions were devoted to the demonstration of
applications and prototypes, and to the final summary of the Workshop
on perspectives on the field.
-
Elisabeth Andre, Wolfgang Finkler, Winfried Graf, Karin Harbusch, Jochen Heinsohn, Anne Kilger, Bernhard Nebel, Hans-Jürgen Profitlich, Thomas Rist, Wolfgang Wahlster, Aandreas Butz and and Aanthony Jameson.
WIP: From Multimedia to Intellimedia (Abstract of Video).
In
Proceedings of the 14th International Joint Conference on
Artificial Intelligence (IJCAI'95), pp. 2053-2054.
Montreal, Canada 1995.
(PDF)
-
Bernd Owsnicki-Klewe, Kai von Luck and Bernhard Nebel.
Wissensrepräsentation und Logik - Eine Einführung.
In
G. Görz (ed.),
Einführung in die Künstliche
Intelligenz, pp. 3-54.
Addison-Wesley, Bonn 1995.
1st edition: 1993.
(Show abstract)
(Hide abstract)
(PDF)
Wir geben eine Einführung in die Modellierung mit Hilfe logischer
Methoden, skizzieren das Design von
Wissensrepräsentationssystemen auf logischer und algorithmischer
Ebene und diskutieren die Umsetzung in Implementationen.
-
Bernhard Nebel.
Base Revision Operations and Schemes: Representation, Semantics and
Complexity.
In
G. della Riccia, R. Kruse and R. Viertl (eds.),
Mathematical and Statistical Methods in Artificial
Intelligence, pp. 157-170.
Springer-Verlag, Wien, New York 1995.
(Show abstract)
(Hide abstract)
The theory of belief revision developed by Gärdenfors
and his colleagues characterizes the classes of reasonable belief
revision operations. However, some of the assumptions made in the
theory of belief revision are unrealistic from a computational point
of view. We address this problem by considering revision operations
that are based on a priority ordering over a set of sentences
representing a belief state instead of using preference relations
over all sentences that are accepted in a belief state. In addition
to providing a semantic justification for such operations, we
investigate also the computational complexity. We show how to
generate an epistemic entrenchment ordering for a belief state from
an arbitrary priority ordering over a set of sentences representing
the belief state and show that the resulting revision is very
efficient. Finally, we show that some schemes for generating
revision operations from bases can encode the preference relations
more concisely than others.
-
Sonia Bergamaschi and Bernhard Nebel.
Acquisition and validation of complex object database schemata supporting multiple inheritance.
Applied Intelligence 4, pp. 185-203. 1994.
(Show abstract)
(Hide abstract)
(Online; DOI)
We present an intelligent tool for the acquisition of object oriented
schemata supporting multiple inheritance, which preserves taxonomy
coherence and performs taxonomic inferences. Its theoretical framework
is based on terminological logics, which have been developed in the
area of artificial intelligence. The framework includes a rigorous
formalization of complex objects, which is able to express cyclic
references on the schema and instance level; a subsumption algorithm,
which computes all implied specialization relationships between types;
and an algorithm to detect incoherent types, i.e., necessarily empty
types. Using results from formal analyses of knowledge representation
languages, we show that subsumption and incoherence detection are
computationally intractable from a theoretical point of view. However,
the problems appear to be feasible in almost all practical cases.
-
Gerhard Lakemeyer and Bernhard Nebel (eds.).
Foundations of Knowledge Representation.
Volume 810 of LNAI.
Springer-Verlag, Berlin, Heidelberg, New York 1994.
(Show abstract)
(Hide abstract)
This collection of thoroughly refereed papers presents
state-of-the-art research results by well-known researchers on the
foundations of knowledge representation and reasoning. In addition,
there are two surveys, one by the volume editors intended as a guide
to this book and another by Shoham and Cousins on mental attitudes. In
total, the volume provides a well-organized report on current research
in knowledge representation, which is one of the central subfields of
AI. Except the surveys, the papers grew out of a workshop on
Theoretical Foundations of Knowledge Representation and Reasoning,
held in conjunction with the 10th European Conference on Artificial
Intelligence (ECAI-92) in Vienna in August 1992.
-
Bernhard Nebel and Leoni Dreschler-Fischer (eds.).
Advances in Artificial Intelligence: Proceedings of the
18th Annual German Conference.
Volume 861 of LNAI.
Springer-Verlag, Berlin, Heidelberg, New York 1994.
(Show abstract)
(Hide abstract)
This volume presents the proceedings of the 18th German Annual
Conference on Artificial Intelligence (KI-94), held in Saarbrücken in
September 1994. Besides the invited paper "AI approaches towards
sensor-based support in road vehicles" by H.-H. Nagel, the book
contains 33 full research papers and 12 poster presentations selected
from a total of 98 contributions, half of them originating from
outside Germany. The papers cover all relevant aspects of AI with a
certain focus on knowledge representation and logical foundations of
AI; further topics covered are neural network applications, logic
programming, natural language, machine learning, and reasoning.
-
Jochen Heinsohn, Daniel Kudenko, Bernhard Nebel and and Hans-Jürgen Profitlich.
An Empirical Analysis of Terminological Representation Systems.
Artificial Intelligence 68, pp. 367-397. 1994.
(Show abstract)
(Hide abstract)
(PDF)
The family of terminological representation systems has its roots in the
representation system KL-ONE. Since the development of KL-ONE more than
a dozen similar representation systems have been developed by various
research groups. These systems vary along a number of dimensions. In this
paper, we present the results of an empirical analysis of six such systems.
Surprisingly, the systems turned out to be quite diverse, leading to
problems when transporting knowledge bases from one system to another.
Additionally, the runtime performance between different systems and
knowledge bases varied more than we expected. Finally, our empirical
runtime performance results give an idea of what runtime performance
to expect from such representation systems. These findings complement
previously reported analytical results about the computational complexity of
reasoning in such systems.
-
Franz Baader, Bernhard Hollunder, Bernhard Nebel, Hans-Jürgen Profitlich and Enrico Franconi.
An Empirical Analysis of Optimization Techniques for Terminological
Representation Systems or ``Making KRIS get a move on''.
Applied Intelligence 4, pp. 109-132. 1994.
(Show abstract)
(Hide abstract)
(PDF)
We consider different methods of optimizing the classification
process of terminological representation systems, and evaluate their
effect on three different types of test data. Though these techniques
can probably be found in many existing systems, until now
there has been no coherent description of these techniques and their impact on
the performance of a system. One goal of this paper is to make such
a description available for future implementors of terminological systems.
Building the optimizations that came off best into
the KRIS system greatly enhanced its efficiency.
-
Bernhard Nebel and Christer Bäckström.
On the Computational Complexity of
Temporal Projection, Planning, and Plan Validation.
Artificial Intelligence 66, pp. 125-160. 1994.
(Show abstract)
(Hide abstract)
(PDF)
One kind of temporal reasoning is temporal projection - the
computation of the consequences of a set of events. This problem is
related to a number of other temporal reasoning tasks such as plan
validation and planning. We show that one particular, simple case of
temporal projection on partially ordered events turns out to be harder
than previously conjectured, while planning is easy under the same
restrictions. Additionally, we show that plan validation is
tractable for an even larger class of plans - the unconditional
plans - for which temporal projection is NP-hard, thus indicating
that temporal projection may not be a necessary ingredient in planning
and plan validation. Analyzing the partial decision procedure for the
temporal projection problem that has been proposed by other authors,
we notice that it fails to be complete for unconditional plans, a case
where we have shown plan validation tractable.
-
Bernhard Nebel.
Base Revision Operations and Schemes: Representation, Semantics and
Complexity.
In
Proceedings of the 11th
European Conference on Artificial Intelligence (ECAI'94), pp. 341-345.
1994.
(Show abstract)
(Hide abstract)
(PDF)
The theory of belief revision developed by Gärdenfors
and his colleagues characterizes the classes of reasonable belief
revision operations. However, some of the assumptions made in the
theory of belief revision are unrealistic from a computational point
of view. We address this problem by considering revision operations
that are based on a priority ordering over a set of sentences
representing a belief state instead of using preference relations
over all sentences that are accepted in a belief state. In addition
to providing a semantic justification for such operations, we
investigate also the computational complexity. We show how to
generate an epistemic entrenchment ordering for a belief state from
an arbitrary priority ordering over a set of sentences representing
the belief state and show that the resulting revision is very
efficient. Finally, we show that some schemes for generating
revision operations from bases can encode the preference relations
more concisely than others.
-
Bernhard Nebel and Hans-Jürgen Bürckert.
Reasoning about Temporal Relations:
A Maximal Tractable Subclass of Allen's Interval Algebra.
In
Proceedings of the 12th National
Conference of the American Association for Artificial Intelligence
(AAAI'94), pp. 356-361.
1994.
(Show abstract)
(Hide abstract)
(PDF)
(TAR.GZ)
We introduce a new subclass of Allen's interval algebra we call
``ORD-Horn subclass,'' which is a strict superset of the ``pointisable
subclass.'' We prove that reasoning in the ORD-Horn subclass is a
polynomial-time problem and show that the path-consistency method is
sufficient for deciding satisfiability. Further, using an extensive
machine-generated case analysis, we show that the ORD-Horn subclass is
a maximal tractable subclass of the full algebra (assuming P=/=NP). In
fact, it is the unique greatest tractable subclass amongst the
subclasses that contain all basic relations.
-
Gerhard Lakemeyer and Bernhard Nebel.
Foundations of Knowledge Representation and Reasoning: A Guide to This Volume.
In
G. Lakemeyer and B. Nebel (eds.),
Foundations of Knowledge Representation and Reasoning, pp. 1-12.
Springer-Verlag, Berlin, Heidelberg, New York 1994.
(Show abstract)
(Hide abstract)
(PDF)
Knowledge representation (KR) is the area of Artificial Intelligence
that deals with the problem of representing, maintaining, and
manipulating knowledge about an application domain. Since virtually
all Artificial Intelligence systems have to address this problem, KR
is one of the central subfields of Artificial Intelligence. While
knowledge about an application domain may be represented in a variety
of forms, e.g., procedurally in form of program code or implicitly as
patterns of activation in a neural network, research in the area of
knowledge representation assumes an explicit and
declarative representation, an assumption that distinguishes KR
from research in, e.g., programming languages and neural networks.
In this paper, we summarize the current state of the art in KR and
classify the contributions in this volume.
-
Bernhard Nebel and Hans-Jürgen Bürckert.
Managing Qualitative Temporal Information: Expressiveness vs. Complexity.
In
K. von Luck and H. Marburger (eds.),
Management and Processing of Complex Data Structures, pp. 104-117.
Springer-Verlag, Berlin, Heidelberg, New York 1994.
(Show abstract)
(Hide abstract)
For natural language understanding and generation, plan generation and
recognition, and knowledge representation, it is necessary to
represent qualitiave temporal information and to reason with it.
Allen's interval calculus provides an appropriate framework for such a
task. We introduce a new subclass of Allen's interval algebra we call
``ORD-Horn subclass,'' which is a strict superset of the ``pointisable
subclass.'' We prove that reasoning in the ORD-Horn subclass is a
polynomial-time problem and show that the path-consistency method is
sufficient for deciding satisfiability. Further, using an extensive
machine-generated case analysis, we show that the ORD-Horn subclass is a
maximal tractable subclass of the full algebra (assuming
P=/=NP). In fact, it is the unique greatest tractable subclass
amongst the subclasses that contain all basic relations.
-
Bernhard Hollunder and Bernhard Nebel.
Second International Conference on Principles of Knowledge Representation and Reasoning (KR'91).
Künstliche Intelligenz 6 (3), pp. 52-53. 1992.
-
Lin Padgham and Bernhard Nebel.
Combining Classification and Nonmonotonic Inheritance Reasoning: A First Step.
In
Issues in Description Logics: Users Meet Developers, AAAI Fall Symposium 1992, pp. 64-71.
AAAI Press 1992.
-
Bernhard Nebel and Charles Rich and William Swartout (eds.).
Principles of Knowledge
Representation and Reasoning: Proceedings of the Third International
Conference (KR'92).
Morgan Kaufmann, Cambridge, MA 1992.
(Show abstract)
(Hide abstract)
The idea of explicit representations of knowledge manipulated by
inference algorithms provides an important foundation for much work in
Artificial Intelligence, from natural language to expert systems. A
growing number of researchers are interested in the principles
governing systems based on this idea. This conference will bring
together these researchers in a more intimate setting than that of the
general AI conferences. In particular, authors will have the
opportunity to give presentations of adequate length to present
substantial results.
The theme of this year's conference is the relationship between the
principles of knowledge representation and reasoning and their
embodiment in working systems.
-
Franz Baader, Bernhard Hollunder, Bernhard Nebel and Hans-Jürgen Profitlich Enrico Franconi.
An Empirical Analysis of Optimization Techniques for Terminological
Representation Systems.
In
Principles of Knowledge Representation and Reasoning: Proceedings
of the Third International Conference (KR'92), pp. 270-281.
Morgan Kaufmann, Cambridge, MA 1992.
(Show abstract)
(Hide abstract)
(PDF)
We consider different methods of optimizing the classification process
of terminological representation systems, and evaluate their effect on
three different types of test data. Though these techniques can
probably be found in many existing systems, until now there has been
no coherent description of these techniques and their impact on the
performance of a system. One goal of this paper is to make such a
description available for future implementors of terminological
systems. Building the optimizations that came off best into the KRIS
system greatly enhanced its efficiency.
-
Christer Bäckström and Bernhard Nebel.
On the Computational Complexity of Planning and Story Understanding.
In
Proceedings of the 10th European Conference
on Artificial Intelligence (ECAI'92), pp. 349-353.
Vienna, Austria 1992.
(Show abstract)
(Hide abstract)
(PDF)
Other authors have shown that temporal projection - the
computation of the consequences for a set of events - is intractable
even for severly restricted cases. They have also suggested that
temporal projection is the basic problem underlying planning, plan
validation, and story understanding. We have earlier shown that plan
validation is actually tractable for a broad and important class of
plans, thus indicating that temporal projection and plan validation
are not as closely related as was believed. In this paper, we show
that also planning and story understanding is sometimes tractable when
temporal projection is intractable. This means that temporal
projcetion is hardly a necessary ingredient of these tasks either.
-
Jochen Heinsohn, Daniel Kudenko, Bernhard Nebel and and Hans-Jürgen Profitlich.
An Empirical Analysis of Terminological Representation Systems.
In
Proceedings of the 10th National Conference of the American
Association for Artificial Intelligence (AAAI'92).
San Jose, CA 1992.
(Show abstract)
(Hide abstract)
(PDF)
The family of terminological representation systems has its roots in
the representation system KL-ONE. Since the development of this
system more than a dozen similar representation systems have been
developed by various research groups. These systems vary along a
number of dimensions. In this paper, we present the results of an
empirical analysis of six such systems. Surprisingly, the systems
turned out to be quite diverse leading to problems when transporting
knowledge bases from one system to another. Additionally, the runtime
performance between different systems and knowledge bases varied more
than we expected. Finally, our empirical runtime performance results
give an idea of what runtime performance to expect from such
representation systems. These findings complement previously reported
analytical results about the computational complexity of reasoning in
such systems.
-
Bernhard Nebel, Christer Bäckström and .
On the Computational Complexity of Temporal Projection and Plan
Validation.
In
Proceedings of the 10th National Conference of
the American Association for Artificial Intelligence (AAAI'92), pp. 748-753.
San Jose, CA 1992.
(Show abstract)
(Hide abstract)
(PDF)
One kind of temporal reasoning is temporal projection - the
computation of the consequences of a set of events. This problem is
related to a number of other temporal reasoning tasks such as
story understanding, planning, and plan validation. We
show that one particular simple case of temporal projection on
partially ordered events turns out to be harder than previously
conjectured. However, given the restrictions of this problem,
story understanding, planning, and plan validation appear to be easy.
In fact, we show that plan validation, one of the intended
applications of temporal projection, is tractable for an even larger
class of plans.
-
Bernhard Nebel.
Computational Complexity and KR&R: Is Polynomial
Time All that Matters?
In
Workshop Notes of the AAAI'92 Workshop on "Tractable Reasoning", pp. 126-129.
San Jose, CA 1992.
(PDF)
-
Bernhard Nebel.
Syntax-Based Approaches to Belief Revision.
In
P. Gärdenfors (ed.),
Belief Revision, pp. 52-88.
Cambridge University Press, Cambridge, UK 1992.
(Show abstract)
(Hide abstract)
(PDF)
Belief revision leads to temporal
nonmonotonicity, i.e., the set of beliefs does not grow monotonically
with time. Default reasoning leads to logical nonmonotonicity,
i.e., the set of consequences does not grow monotonically with the set
of premises. The connection between these forms of nonmonotonicity
will be studied in this paper focusing on syntax-based approaches.
It is shown that a general form of syntax-based belief revision
corresponds to a special kind of partial meet revision in the sense of
the theory of epistemic change, which in turn is expressively
equivalent to some variants of logics for default reasoning.
Additionally, the computational complexity of the membership problem
in revised belief sets and of the equivalent problem of derivability
in default logics is analyzed, which turns out to be located at the
lower end of the polynomial hierarchy.
-
Jochen Heinsohn, Daniel Kudenko, Bernhard Nebel and Hans-Jürgen Profitlich.
An Empirical Analysis of Terminological Representation Systems,.
In
C. Peltason and K. von Luck and C. Kindermann (eds.),
Terminological Logic Users Workshop - Proceedings, pp. 15-26.
Berlin, Germany 1991.
KIT Report 95.
-
Bernhard Nebel.
Belief Revision and Default Reasoning: Syntax-Based
Approaches.
In
Proceedings of the Second International Conference on Principles of
Knowledge Representation and Reasoning (KR'91), pp. 417-428.
Cambridge, MA 1991.
(Show abstract)
(Hide abstract)
(PDF)
Belief revision leads to temporal nonmonotonicity, i.e., the
set of beliefs does not grow monotonically with time. Default
reasoning leads to logical nonmonotonicity, i.e., the set of
consequences does not grow monotonically with the set of premises. The
connection between these forms of nonmonotonicity will be studied in
this paper focusing on syntax-based approaches. It is shown that a
general form of syntax-based belief revision corresponds to a special
kind of partial meet revision in the sense of the theory of epistemic
change, which in turn is expressively equivalent to some variants of
logics for default reasoning. Additionally, the computational
complexity of the membership problem in revised belief sets and of the
equivalent problem of derivability in default logics is analyzed,
which turns out to be located at the lower end of the polynomial
hierarchy.
-
Bernhard Nebel, Kai von Luck and and Christof Peltason (eds.).
International Workshop on Terminological Logics.
DFKI Document
D-91-13,
DFKI, Saarbrücken, 1991.
Also: KIT Report 89, Fachbereich Informatik, Technische
Universität Berlin and IWBS Report, IBM Deutschland, Stuttgart.
(Show abstract)
(Hide abstract)
The report is a compilation of working papers submitted to the
``Second International Workshop on Terminological Logics'' held at
Schloß Dagstuhl near Saarbrücken, Germany, on May 6-8, 1991. The
workshop brought together 40 invited participants currently working in
the field, and served to provide a snapshot of the current state of
research. As documented by the variety of talks, the aspects of
theoretical work (semantical foundations, complexity), system-oriented
work (implementations), and application-oriented work are all dealt
with within one community. In character with the informal nature of
the workshop, these papers sketch personal interests, work in
progress, or summaries of research results rather than being fully
elaborated articles.
-
Jochen Heinsohn, Daniel Kudenko, Bernhard Nebel and Hans-Jürgen Profitlich.
Integration of Action Representation in Terminological Logics.
In
C. Peltason, K. von Luck and C. Kindermann (eds.),
Terminological Logic Users Workshop - Proceedings.
Berlin, Germany 1991.
KIT Report 95.
-
Hans-Jürgen Profitlich, Jochen Heinsohn, Daniel Kudenko and Bernhard Nebel.
A Comparative Analysis of Terminological Representation Systems.
In
Working Notes of the AAAI Spring Symposium 1991 on
"Implemented Knowledge Representation Systems", pp. 347-360.
Stanford University, Stanford, CA 1991.
-
Sonia Bergamaschi and Bernhard Nebel.
The Complexity of Multiple Inheritance in Complex
Object Data Models.
In
Workshop Notes of the IJCAI'91 Workshop on "Objects
and AI".
Sydney, Australien 1991.
(Show abstract)
(Hide abstract)
(PDF)
We specify a data model for complex objects, following closely recent
approaches in the areas of object-oriented and deductive database research. The
main extensions with respect to previous proposals are, firstly,
the conjunction operator, which permits one to express
multiple inheritance between types
as a semantic property, and, secondly, a distinction between
primitive and derived classes, the latter corresponding
to database views. We sketch how such a data model can be exploited in schema
design and specify an algorithm for computing specialization relationships
between classes. Using results from formal analyses of
knowledge representation languages, we note that the computational
properties of interesting problems, such as detection of emptiness
of a class interpretation and computation of a specialization ordering,
appear to be computationally intractable from a theoretical point of view,
but are feasible in almost all practical cases.
-
Franz Baader, Hans-Jürgen Bürckert, Jochen Heinsohn, Bernhard Hollunder, Jürgen
Müller, Bernhard Nebel, Werner Nutt and Hans-Jürgen Profitlich.
Terminological Knowledge Representation: A proposal for a Terminological Logic.
In
B. Nebel, K. von Luck and and C. Peltason (eds.),
International Workshop on Terminological Logics, pp. 120-128.
Dagstuhl, Germany 1991.
DFKI Document D-91-13.
(Show abstract)
(Hide abstract)
(PDF)
This paper contains a proposal for a terminological logic. The formalisms for representing knowledge as well as the needed inferences are described.
-
Bernhard Nebel, Kai von Luck and Christof Peltason (eds.).
International Workshop on Terminological Logics.
Dagstuhl-Seminar-Report
12 (9119),
Schloss Dagstuhl, 1991.
(Show abstract)
(Hide abstract)
(PDF)
The International Workshop on Terminological Logics was the
follow-up event to the ``Workshop on Term Subsumption Languages'' held
in Jackson Village, New Hampshire, in October 1989 (cf. The AI Magazine
11(2)).
Terminological Logics consists of a family of representation
formalisms that grew out of the KL-ONE knowledge representation
system. Unlike some other areas of knowledge representation, in this
field the aspects of theoretical work (semantical foundations,
complexity), system-oriented work (implementational issues), and
application-oriented work are all dealt with within one community, as
documented by the variety of talks at this workshop.
The workshop itself brought together 40 invited participants currently
working in the field, and served to provide a snapshot of the current
state of research, showing that there has been a lot of progress in
the last several years. The theoretical area has advanced to a point
where only a few questions concerning the core formalism remain open.
The current trend seems to be to integrate more functionality and
other formalisms.
In addition to the scheduled sessions, there were a number of informal
meetings for exchanging ideas and planning future collaborative work,
including one about future system standards and standard notation.
This should make the exchange of ideas, systems, and knowledge bases,
and the maintainance of a test corpus easier in the future.
The program was rounded off by an overview talk by Ron Brachman on the
past and future development of Terminological Logics (the issue of
finding a good name for the field is still in discussion), and a panel
debate on aspects of the relationship between ``Theory and Practice''.
-
Bernhard Nebel and Gert Smolka.
Attributive Description Formalisms ... and the Rest of the World.
In
O. Herzog and C.-R. Rollinger (eds.),
Textunderstanding in LILOG: Integrating Computational Linguistics
and Artificial Intelligence, pp. 439-452.
Springer-Verlag, Berlin 1991.
(Show abstract)
(Hide abstract)
(PDF)
Research in knowledge representation has led to the development of
so-called terminological logics, the purpose of which is to support
the representation of the conceptual and terminological part of
Artificial Intelligence applications. Independently, in computational
linguistics, so-called feature logics have been developed which are
aimed at representing the semantic and syntactic information natural
language sentences convey. Since both of these logics rely mainly on
attributes as the primary notational primitives for representing
knowledge, they can be jointly characterized as attributive
description formalisms.
Although the intended applications for terminological logics and
feature logics are not identical, and the computational services of
systems based on the respective formalisms are quite different for
this reason, the logical foundations turn out to be very similar - as
we pointed out elsewhere. In this paper, we will show how attributive
description formalisms relate to ``the rest of the world.'' Recently,
a number of formal results in the area of attributive description
formalisms have been obtained by exploiting other research fields,
such as formal language theory, automata theory, and modal
logics. This connection between these different fields of formal
research will be highlighted in the sequel.
-
Bernhard Nebel and Christof Peltason.
Terminological Reasoning and Information
Management.
In
D. Karagianis (ed.),
Artificial Intelligence and Information Systems: Integration Aspects, pp. 181-212.
Springer-Verlag, Berlin 1991.
(Show abstract)
(Hide abstract)
(PDF)
Reasoning with terminological logics is a subfield in the area of knowledge
representation that evolved from the representation language
KL-ONE. Its main purpose is to automatically determine the location of a
a new concept description (or object description) in a partially
ordered set of given concepts. It seems to be a promising approach
to apply the
techniques developed in this area to the development of new
object-based database models. The main advantages are a uniform
query and database definition language and the utilization of an indexing
technique, which we call semantic indexing.
-
Bernhard Nebel.
Terminological Cycles: Semantics and Computational Properties.
In
J. Sowa (ed.),
Principles of Semantic Networks, pp. 331-362.
Morgan Kaufmann, San Mateo 1991.
(Show abstract)
(Hide abstract)
(PDF)
Terminological knowledge representation formalisms are intended to
capture the analytic relationships between terms of a
vocabulary intended to describe a domain.
A term whose definition refers, either directly or indirectly, to
the term itself presents a problem for most terminological representation
systems because it is obvious neither whether such a term is meaningful, nor
how it could be handled by a knowledge representation system in a satisfying
manner. After some examples of intuitively sound terminological
cycles are given, different formal semantics are investigated and
evaluated with respect to the examples. As it turns out, none of the
different styles of semantics
seems to be completely satisfying for all purposes.
Finally, consequences in terms of computational complexity and
decidability are discussed.
-
Jürgen Müller, Franz Baader, Bernhard Nebel, Werner Nutt and Gert Smolka:.
Tutorial on Reasoning and Representation with Concept Languages.
In
10th International Conference on Automated Deduction (CADE-90), p. 681.
Springer 1990.
-
Peter F. Patel-Schneider, Bernd Owsnicki-Klewe, Alfred Kobsa, Nicola Guarino, Robert M. MacGregor, William S. Mark, Deborah L. McGuinness, Bernhard Nebel, Albrecht Schmiedel and John Yen.
Term Subsumption Languages in Knowledge Representation.
AI Magazine 11 (2). 1990.
(Show abstract)
(Hide abstract)
(Online; DOI)
The Workshop on Term Subsumption Languages in Knowledge Representa- tion was held 18–20 October 1989 at the Inn at Thorn Hill, located in the White Mountain region of New Hamp- shire. The workshop was organized by Peter F. Patel-Schneider of AT&T Bell Laboratories, Murray Hill, New Jersey; Marc Vilain of MITRE, Bedford, Massachusetts; Ramesh S. Patil of the Massachusetts Institute of Technolo- gy (MIT); and Bill Mark of the Lock- heed AI Center, Menlo Park, California. Support was provided by the Ameri- can Association for Artificial Intelli- gence and AT&T Bell Laboratories.
This workshop was the latest in a series in this area. Previous workshops have had a slightly narrower focus, being explicitly concerned with KL- One, the first knowledge representa- tion system based on a term subsump- tion language (TSL), or its successor, NIKL. Two of these workshops were held in 1981 (Schmolze and Brach- man 1982) and 1986 (Moore 1986).
The workshop brought together 34 researchers and students in the field from the United States, Germany, Austria, Italy, Canada, and Korea. Its primary goal was to review the field after about 10 years of work, exchange ideas, and set up research directions for the future.
-
Bernhard Nebel.
Reasoning and Revision in Hybrid Representation Systems.
Volume 422 of LNAI.
Springer-Verlag, Berlin, Heidelberg, New York 1990.
(Show abstract)
(Hide abstract)
(PDF)
The dynamic aspects of knowledge representation systems, namely,
reasoning with represented knowledge and revising
represented knowledge, are the most important aspects of such systems.
In this book, these aspects are investigated
in the context of hybrid representation
systems based on KL-ONE.
After a general introduction to knowledge representation, reasoning,
and revision, a typical member of the family of hybrid
representation systems based on KL-ONE is introduced and
analyzed from a semantic and algorithmic point of view. This analysis
leads to new complexity results about subsumption determination and
a characterization of a proposed hybrid inference algorithm as
conditionally complete. Additionally, it is shown that so-called
terminological cycles can be integrated smoothly into the framework.
Based on the analysis of representation and reasoning in
KL-ONE-based systems,
the revision problem is investigated. A survey of some
approaches to belief revision leads to a reconstruction of
symbol-level belief revision on the knowledge level.
A conceptual analysis of
terminological revision
demonstrates that belief revision
techniques developed for the revision of assertional knowledge are
not adequate for the revision of terminological knowledge. For this
reason, a literal revision approach is adopted.
Essentially, it amounts to minimal mutilations in the
literal description of definitions. Finally, implementation
techniques for terminological revision operations are described, and the interface
problem for a knowledge acquisition system is discussed.
This is a reprint of the revised version of
my dissertation accepted by the University of Saarland in 1989, which has been
published by Springer-Verlag in 1990. I created this
reprint with permission by Springer-Verlag
because the book is out of print since fall 1994.
The reprint is almost identical to the book. The page
numbering is different, the format of the bibliography differs from
the book and the reprint version does not contain an author
index. Otherwise the contents is the same, however.
-
Bernhard Nebel.
Terminological Reasoning is Inherently
Intractable.
Artificial Intelligence 43, pp. 235-249. 1990.
(Show abstract)
(Hide abstract)
(PDF)
Computational tractability has been a major concern in the area of
terminological knowledge representation and reasoning. However, all
analyses of the computational complexity of terminological reasoning
are based on the hidden assumption that subsumption in terminologies
reduces to subsumption of concept descriptions without a significant
increase in computational complexity. In this paper it will be shown
that this assumption, which seems to work in the ``normal case,'' is
nevertheless wrong. Subsumption in terminologies turns out to be
co-NP-complete for a minimal terminological representation language
that is a subset of every useful terminological language.
-
Sonia Bergamaschi and Bernhard Nebel.
Theoretical Foundations of Complex Object Data Models.
Technical Report 74,
CIOC-CNR, Universita di Bologna, Italy, 1990.
(Show abstract)
(Hide abstract)
We specify a data model for complex objects, following closely recent
approaches in object-oriented and deductive database research areas.
The main extensions with respect to previous proposals are: the
conjunction operator, which permits to express inheritance between
classes (types) as a semantic property, and derived classes, which
allows the automatic placement of classes in a specialization
hierarchy. Using results from formal analyses of knowledge
representation languages, we note that the computational properties of
interesting problems, such as detection of emptiness of a class
extension and computation of a specialization ordering, appear to be
computationally intractable. This result applies to syntactical
treatments of inheritance as well. We conclude that in most cases,
schema specifications are almost normalized, thus allowing polynomial
algorithms.
-
Bernhard Nebel and Gert Smolka.
Representation and Reasoning with Attributive Descriptions.
In
K.-H. Bläsius, U. Hedtstück and C. Rollinger (eds.),
Sorts and Types in Artificial Intelligence, pp. 112-139.
Springer-Verlag, Berlin 1990.
(Show abstract)
(Hide abstract)
(PDF)
This paper surveys terminological representation languages and
feature-based unification grammars pointing out the similarities and
differences between these two families of attributive
description formalisms. Emphasis is given to the logical foundations
of these formalisms.
