-
Roman Barták, Simona Ondrčková, Gregor Behnke and Pascal Bercher.
Correcting Hierarchical Plans by Action Deletion.
In
Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR-2021).
2021.
(PDF)
-
Roman Barták, Simona Ondrčková, Gregor Behnke and Pascal Bercher.
Correcting Hierarchical Plans by Action Deletion.
In
Proceedings of the Fourth ICAPS Workshop on Hierarchical Planning.
2021.
(PDF)
-
Roman Barták, Simona Ondrčková, Gregor Behnke and Pascal Bercher.
On the Verification of Totally-Ordered HTN Plans.
In
Proceedings of the Fourth ICAPS Workshop on Hierarchical Planning, pp. 44-48.
2021.
(PDF)
-
Daniel Höller, Julia Whichlacz, Pascal Bercher and Gregor Behnke.
Compiling HTN Plan Verification Problems into HTN Planning Problems.
In
Proceedings of the Fourth ICAPS Workshop on Hierarchical Planning, pp. 8-15.
2021.
(PDF)
-
Pascal Bercher, Gregor Behnke, Matthias Kraus, Marvin Schiller, Dietrich Manstetten, Michael Dambier, Michael Dorna, Wolfgang Minker, Birte Glimm and Susanne Biundo.
Do It Yourself, but Not Alone: Companion-Technology for Home Improvement - Bringing a Planning-Based Interactive DIY Assistant to Life.
Künstliche Intelligenz -- Special Issue on NLP and Semantics. 2021.
(Show abstract)
(Hide abstract)
We report on the technology transfer project "Do it
yourself, but not alone: Companion-Technology for Home Improvement" that
was carried out by Ulm University in cooperation with Robert Bosch GmbH.
We developed a prototypical assistance system that assists a Do It
Yourself (DIY) handyman in carrying out DIY projects. The assistant,
based on various AI and dialog management capabilities, generates a
sequence of detailed instructions that users may just follow or adapt
according to their individual preferences. It features explanation
capabilities as well as pro-active support based on communication with
the user as well as with the involved tools. We report on the project’s
main achievements, including the findings of various empirical studies
conducted in various development stages of the prototype.
-
Gregor Behnke.
Block Compression and Invariant Pruning for SAT-based Totally-Ordered HTN Planning.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 25-35.
2021.
(Show abstract)
(Hide abstract)
(PDF)
Translations into propositional logic are currently one of the most efficient techniques for solving Totally-Ordered HTN planning problems.
The current encodings iterate over the maximum allowed depth of decomposition.
Given this depth, they compute a tree that represents all possible decompositions up to this depth.
Based on this tree, a formula in propositional logic is created.
We show that much of the computed tree is actually useless as it cannot possibly belong to a solution.
We provide a technique for removing (parts of) these useless structures using state invariants.
We further show that is often not necessary to encode all leafs of this tree as separate timesteps, as the prior encodings did.
Instead, we can compress the leafs into blocks and encode all leafs of a block as one timestep.
We show that these changes provide an improvement over the state-of-the-art in HTN planning.
-
Daniel Höller and Gregor Behnke.
Loop Detection in the PANDA Planning System.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 168-173.
2021.
(Show abstract)
(Hide abstract)
(PDF)
The International Planning Competition (IPC) in 2020 was the first one for a long time to host tracks on Hierarchical Task Network (HTN) planning. HyperTensioN, the winner of the tack on totally-ordered problems, comes with an interesting technique: it stores parts of the decomposition path in the state to mark expanded tasks and forces its depth first search to leave recursive structures in the hierarchy. This can be seen as a form of loop detection (LD) -- a technique that is not very common in HTN planning. This might be due to the spirit of encoding enough advice in the model to find plans (so that loop detection is simply not necessary), or because it becomes a computationally hard task in the general (i.e. partially-ordered) setting.
We integrated several approximate and exact techniques for LD into the progression search of the HTN planner PANDA. We test our techniques on the benchmark set of the IPC 2020. Both in the partial ordered and total ordered track, PANDA with LD performs better than the respective winner of the competition.
-
Daniel Höller, Gregor Behnke, Pascal Bercher and Susanne Biundo.
The PANDA Framework for Hierarchical Planning.
KI - Künstliche Intelligenz. 2021.
(Online)
-
Gregor Behnke and David Speck.
Symbolic Search for Optimal Total-Order HTN Planning.
In
Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), p. 11744–11754.
2021.
(Show abstract)
(Hide abstract)
(PDF)
Symbolic search has proven to be a useful approach to optimal classical planning. In Hierarchical Task Network (HTN) planning, however, there is little work on optimal planning. One reason for this is that in HTN planning, most algorithms are based on heuristic search, and admissible heuristics have to incorporate the structure of the task network in order to be informative. In this paper, we present a novel approach to optimal (totally-ordered) HTN planning, which is based on symbolic search. An empirical analysis shows that our symbolic approach outperforms the current state of the art for optimal totally-ordered HTN planning.
-
Matthias Kraus, Marvin Schiller, Gregor Behnke, Pascal Bercher, Michael Dorna, Michael Dambier, Birte Glimm, Susanne Biundo and Wolfgang Minker.
``Was that successful?'' On Integrating Proactive Meta-Dialogue in a DIY-Assistant using Multimodal Cues.
In
Proceedings of the 2020 International Conference on Multimodal Interaction (ICMI 2020).
2020.
(PDF)
-
Daniel Höller, Pascal Bercher, Gregor Behnke and Susanne Biundo.
HTN Plan Repair via Model Transformation.
In
Proceedings of the 42+1st Annual German Conference on Artificial Intelligence (KI 2020).
2020.
(PDF)
-
Daniel Höller, Pascal Bercher and Gregor Behnke.
Delete- and Ordering-Relaxation Heuristics for HTN Planning.
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2020).
2020.
-
Roman Bartak, Simona Ondrckova, Adrien Maillard, Gregor Behnke and Pascal Bercher.
A Novel Parsing-based Approach for Verification of Hierarchical Plans.
In
Proceedings of the 32nd International Conference on Tools with Artificial Intelligence (ICTAI 2020).
2020.
-
Daniel Höller, Pascal Bercher, Gregor Behnke and Susanne Biundo.
HTN Planning as Heuristic Progression Search.
Journal of Artificial Intelligence Research, pp. 835-880. 2020.
-
Gregor Behnke, Pascal Bercher, Matthias Kraus, Marvin Schiller, Kristof Mickeleit, Häge Timo, Michael Dorna, Michael Dambier, Wolfgang Minker, Birte Glimm and Susanne Biundo.
New Developments for Robert - Assisting Novice Users Even Better in DIY Projects.
In
Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 343-347.
2020.
(PDF)
-
Daniel Höller, Gregor Behnke, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier and Ron Alford.
HDDL - A Language to Describe Hierarchical Planning Problems.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 6-17.
2020.
(PDF)
-
Gregor Behnke, Daniel Höller, Alexander Schmid, Pascal Bercher and Susanne Biundo.
On Succinct Groundings of HTN Planning Problems.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9775-9784.
2020.
(Show abstract)
(Hide abstract)
(PDF)
Both search-based and translation-based planning systemsusually operate on grounded representations of the problem. Planning models, however, are commonly defined using lifted description languages. Thus, planning systems usually generate a grounded representation of the lifted model as a pre-processing step. For HTN planning models, only one method to ground lifted models has been published so far. In this paper we present a new approach for grounding HTN planning problems that produces smaller groundings in a shorter timespan than the previously published method.
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
Finding Optimal Solutions in HTN Planning - A SAT-based Approach.
In
Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 5500-5508.
2019.
(PDF)
-
Gregor Behnke, Marvin Schiller, Matthias Kraus, Pascal Bercher, Mario Schmautz, Michael Dorna, Michael Dambier, Wolfgang Minker, Birte Glimm and Susanne Biundo.
Alice in DIY-Wonderland or: Instructing novice users on how to use tools in DIY projects.
AI Communications, pp. 31-57. 2019.
(PDF)
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
Bringing Order to Chaos - A Compact Representation of Partial Order in SAT-based HTN Planning.
In
Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), pp. 7520-7529.
2019.
(PDF)
-
Daniel Höller, Pascal Bercher, Gregor Behnke and Susanne Biundo.
On Guiding Search in HTN Planning with Classical Planning Heuristics.
In
Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019).
2019.
(PDF)
-
Gregor Behnke, Daniel Höller, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier and Ron Alford.
Hierarchical Planning in the IPC.
In
Proceedings of 2019 Workshop on the International Planning Competition (WIPC 2019), pp. 40-47.
2019.
(PDF)
-
Daniel Höller, Gregor Behnke, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier and Ron Alford.
HDDL - A Language to Describe Hierarchical Planning Problems.
In
Proceedings of the Second ICAPS Workshop on Hierarchical Planning, pp. 6-17.
2019.
(PDF)
-
Gregor Behnke, Daniel Höller, Pascal Bercher and Susanne Biundo.
More Succinct Grounding of HTN Planning Problems - Preliminary Results.
In
Proceedings of the Second ICAPS Workshop on Hierarchical Planning, pp. 40-48.
2019.
(PDF)
-
Matthias Kraus, Gregor Behnke, Pascal Bercher, Marvin Schiller, Susanne Biundo, Birte Glimm and Wolfgang Minker.
A Multimodal Dialogue Framework for Cloud-Based Companion Systems.
In
Proceedings of the 9th International Workshop on Spoken Dialogue Systems Technology (IWSDS 2018), pp. 405-410.
2018.
(PDF)
-
Marvin Schiller, Gregor Behnke, Pascal Bercher, Matthias Kraus, Michael Dorna, Felix Richter, Susanne Biundo, Birte Glimm and Wolfgang Minker.
Evaluating Knowledge-Based Assistance for DIY.
In
Proceedings of MCI Workshop ``Digital Companion'', pp. 925-930.
2018.
(PDF)
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
Tracking Branches in Trees - A Propositional Encoding for solving Partially-Ordered HTN Planning Problems.
In
Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI 2018), pp. 73-80.
2018.
(PDF)
-
Gregor Behnke and Susanne Biundo.
X and more Parallelism: Integrating LTL-Next into SAT-based Planning with Trajectory Constraints While Allowing for Even More Parallelism.
Inteligencia Artificial 21(62), pp. 75-90. 2018.
(PDF)
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
totSAT - Totally-Ordered Hierarchical Planning through SAT.
In
Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pp. 6110-6118.
2018.
(PDF)
-
Gregor Behnke, Marvin Schiller, Matthias Kraus, Pascal Bercher, Mario Schmautz, Michael Dorna, Wolfgang Minker, Birte Glimm and Susanne Biundo.
Instructing Novice Users on How to Use Tools in DIY Projects.
In
Proceedings of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI 2018), pp. 5805-5807.
2018.
(PDF)
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
Tracking Branches in Trees - A Propositional Encoding for solving Partially-Ordered HTN Planning Problems.
In
Proceedings of the First ICAPS Workshop on Hierarchical Planning, pp. 40-47.
2018.
(PDF)
-
Daniel Höller, Pascal Bercher, Gregor Behnke and Susanne Biundo.
HTN Plan Repair Using Unmodified Planning Systems.
In
Proceedings of the First ICAPS Workshop on Hierarchical Planning, pp. 26-30.
2018.
(PDF)
-
Gregor Behnke and Susanne Biundo.
X and more Parallelism - Integrating LTL-Next into SAT-based Planning with Trajectory Constraints while Allowing for even more Parallelism.
In
Proceedings of the Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS 2018), pp. 1-10.
2018.
(PDF)
-
Daniel Höller, Gregor Behnke, Pascal Bercher and Susanne Biundo.
Plan and Goal Recognition as HTN Planning.
In
Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI 2018), pp. 466-473.
2018.
(PDF)
-
Daniel Höller, Pascal Bercher, Gregor Behnke and Susanne Biundo.
A Generic Method to Guide HTN Progression Search with Classical Heuristics.
In
Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018), pp. 114-122.
2018.
(PDF)
-
Daniel Höller, Pascal Bercher, Gregor Behnke and Susanne Biundo.
Plan and Goal Recognition as HTN Planning.
In
Proceedings of the AAAI 2018 Workshop on Activity Plan and Intent Recognition (PAIR 2018), pp. 607-613.
2018.
(PDF)
-
Benedikt Leichtmann, Pascal Bercher, Daniel Höller, Gregor Behnke, Susanne Biundo, Verena Nitsch and Martin Baumann.
Towards a Companion System Incorporating Human Planning Behavior - A Qualitative Analysis of Human Strategies.
In
Proceedings of the 3rd Transdisciplinary Conference on Support Technologies (TCST 2018), pp. 89-98.
2018.
(PDF)
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
This is a solution! (... but is it though?) - Verifying solutions of hierarchical planning problems.
In
Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017), pp. 20-28.
2017.
(PDF)
-
Florian Nothdurft, Pascal Bercher, Gregor Behnke and Wolfgang Minker.
User Involvement in Collaborative Decision-Making Dialog Systems.
In
Dialogues with Social Robots: Analyses Enablements and Evaluation, pp. 129-141.
2017.
(PDF)
-
Pascal Bercher, Gregor Behnke, Daniel Höller and Susanne Biundo.
An Admissible HTN Planning Heuristic.
In
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), pp. 480-488.
2017.
(PDF)
-
Marvin Schiller, Gregor Behnke, Mario Schmautz, Pascal Bercher, Matthias Kraus, Michael Dorna, Wolfgang Minker, Birte Glimm and Susanne Biundo.
A Paradigm for Coupling Procedural and Conceptual Knowledge in Companion Systems.
In
Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017).
2017.
(PDF)
-
Gregor Behnke, Benedikt Leichtmann, Pascal Bercher, Daniel Höller, Verena Nitsch, Martin Baumann and Susanne Biundo.
Help me make a dinner! Challenges when assisting humans in action planning.
In
Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017).
2017.
(PDF)
-
Gregor Behnke, Florian Nielsen, Marvin Schiller, Pascal Bercher, Matthias Kraus, Birte Glimm, Wolfgang Minker and Susanne Biundo.
SLOTH - the Interactive Workout Planner.
In
Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017).
2017.
(PDF)
-
Pascal Bercher, Daniel Höller, Gregor Behnke and Susanne Biundo.
User-Centered Planning.
In
Companion Technology - A Paradigm Shift in Human-Technology Interaction, pp. 79-100.
2017.
(PDF)
-
Pascal Bercher, Felix Richter, Thilo Hörnle, Thomas Geier, Daniel Höller, Gregor Behnke, Florian Nielsen, Frank Honold, Schüssel Felix, Stephan Reuter, Wolfgang Minker, Michael Weber, Klaus Dietmayer and Susanne Biundo.
Advanced User Assistance for Setting Up a Home Theater.
In
Companion Technology - A Paradigm Shift in Human-Technology Interaction, pp. 485-491.
2017.
(PDF)
-
Gregor Behnke, Florian Nielsen, Marvin Schiller, Denis Ponomaryov, Pascal Bercher, Birte Glimm, Wolfgang Minker and Susanne Biundo.
To Plan for the User Is to Plan With the User - Integrating User Interaction Into the Planning Process.
In
Companion Technology - A Paradigm Shift in Human-Technology Interaction, pp. 123-144.
2017.
(PDF)
-
Pascal Bercher, Felix Richter, Frank Honold, Florian Nielsen, Felix Schüssel, Thomas Geier, Thilo Hörnle, Stephan Reuter, Daniel Höller, Gregor Behnke, Klaus Dietmayer, Wolfgang Minker, Michael Weber and Susanne Biundo.
A Companion-System Architecture for Realizing Individualized and Situation-Adaptive User Assistance.
In
Technical Report - Ulm University.
2018.
(PDF)
-
Gregor Behnke, Daniel Höller, Pascal Bercher and Susanne Biundo.
Change the Plan - How hard can that be?
In
Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), pp. 38-46.
2016.
(PDF)
-
Daniel Höller, Gregor Behnke, Pascal Bercher and Susanne Biundo.
Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages.
In
Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), pp. 158-165.
2016.
(PDF)
-
Ron Alford, Gregor Behnke, Daniel Höller, Pascal Bercher, Susanne Biundo and David W. Aha.
Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems.
In
Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), pp. 20-28.
2016.
(PDF)
-
Pascal Bercher, Daniel Höller, Gregor Behnke and Susanne Biundo.
More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks.
In
Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), pp. 225-233.
2016.
(PDF)
-
Gregor Behnke, Daniel Höller and Susanne Biundo.
On the Complexity of HTN Plan Verification and Its Implications for Plan Recognition.
In
Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), pp. 25-33.
2015.
(PDF)
-
Gregor Behnke, Denis Ponomaryov, Marvin Schiller, Ber\-cher Pascal, Florian Nothdurft, Birte Glimm and Susanne Biundo.
Coherence Across Components in Cognitive Systems - One Ontology to Rule Them All.
In
Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 1442-1449.
2015.
(PDF)
-
Florian Nothdurft, Gregor Behnke, Pascal Bercher, Susanne Biundo and Wolfgang Minker.
The Interplay of User-Centered Dialog Systems and AI Planning.
In
Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue (SIGDIAL 2015), pp. 344-353.
2015.
(PDF)
-
Pascal Bercher, Felix Richter, Thilo Hörnle, Thomas Geier, Daniel Höller, Gregor Behnke, Florian Nothdurft, Frank Honold, Wolfgang Minker, Michael Weber and Susanne Biundo.
A Planning-based Assistance System for Setting Up a Home Theater.
In
Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), pp. 4264-4265.
2015.
(PDF)
-
Gregor Behnke, Pascal Bercher, Susanne Biundo, Birte Glimm, Denis Ponomaryov and Marvin Schiller.
Integrating Ontologies and Planning for Cognitive Systems.
In
Proceedings of the 28th International Workshop on Description Logics (DL 2015), pp. 338-360.
2015.
(PDF)
-
Pascal Bercher, Daniel Höller, Gregor Behnke and Susanne Biundo.
User-Centered Planning - A Discussion on Planning in the Presence of Human Users.
In
Proceedings of the First International Symposium on Companion Technology (ISCT 2015), pp. 79-82.
2015.
(PDF)
-
Gregor Behnke, Marvin Schiller, Denis Ponomaryov, Florian Nothdurft, Ber\-cher Pascal, Wolfgang Minker, Birte Glimm and Susanne Biundo.
A Unified Knowledge Base for Companion-Systems - A Case Study in Mixed-Initiative Planning.
In
Proceedings of the First International Symposium on Companion Technology (ISCT 2015), pp. 43-48.
2015.
(PDF)
-
Daniel Höller, Gregor Behnke, Pascal Bercher and Susanne Biundo.
Language Classification of Hierarchical Planning Problems.
In
Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 447-452.
2014.
(PDF)
-
David Speck, Christian Dornhege and Wolfram Burgard.
Shakey 2016 - How Much Does it Take to Redo Shakey the Robot?
IEEE Robotics and Automation Letters (RA-L) 2 (2), pp. 1203-1209. 2017.
(Show abstract)
(Hide abstract)
(PDF; Online)
Shakey the robot was one of the first autonomous
robots that showed impressive capabilities of navigation and mobile
manipulation. Since then, robotics research has made great
progress, showing more and more capable robotic systems for a
large variety of application domains and tasks. In this letter, we
look back on decades of research by rebuilding Shakey with modern
robotics technology in the open-source Shakey 2016 system.
Hereby, we demonstrate the impact of research by showing that
ideas from the original Shakey are still alive in state-of-the-art systems,
while robotics in general has improved to deliver more robust
and more capable software and hardware. Our Shakey 2016 system
has been implemented on real robots and leverages mostly
open-source software. We experimentally evaluate the system in
real-world scenarios on a PR2 robot and a Turtlebot-based robot
and particularly investigate the development effort. The experiments
documented in this letter demonstrate that results from
robotics research are readily available for building complex robots
such as Shakey within a short amount of time and little effort.
-
Christian Dornhege, Alexander Kleiner, Andreas Hertle and Andreas Kolling.
Multirobot Coverage Search in Three Dimensions.
Journal of Field Robotics 33 (4), pp. 537-558. 2016.
(Show abstract)
(Hide abstract)
(PDF)
Searching for objects and observing parts of a known environment efficiently is a fundamental problem in
many real-world robotic applications, e.g., household robots searching for objects, inspection robots searching
for leaking pipelines, and rescue robots searching for survivors after a disaster. We consider the problem of
identifying and planning sequences of sensor locations from which robot sensors can observe and cover complex
three-dimensional (3D) environments while traveling only short distances. Our approach is based on sampling
and ranking a large number of sensor locations for a 3D environment represented by an OctoMap. The visible
area from these sensor locations induces a minimal partition of the 3D environment that we exploit for planning
sequences of sensor locations with short travel times efficiently. We present multiple planning algorithms
designed for single robots and for multirobot teams. These algorithms include variants that are greedy, optimal,
or based on decomposing the planning problem into a set cover and traveling salesman problem. We evaluated
and compared these algorithms empirically in simulation and real-world robot experiments with up to four
robots. Our results demonstrate that, despite the intractability of the overall problem, computing and executing
effective solutions for multirobot coverage search in real 3D environments is feasible and ready for real-world
applications.
-
Armin Hornung, Sebastian Boettcher, Christian Dornhege, Andreas Hertle, Jonas Schlagenhauf and Maren Bennewitz.
Mobile Manipulation in Cluttered Environments with Humanoids: Itegrated Perception, Task Planning, and Action Execution.
In
Proceedings of the IEEE-RAS International Conference on Humanoid Robots (HUMANOIDS).
2014.
(Show abstract)
(Hide abstract)
(PDF)
To autonomously carry out complex mobile manipulation tasks, a robot control system has to integrate several components for perception, world modeling, action planning and replanning, navigation, and manipulation. In this paper, we present a modular framework that is based on the Temporal Fast Downward Planner and supports external modules to control the robot. This allows to tightly integrate individual sub-systems with the high-level symbolic planner and enables a humanoid robot to solve challenging mobile manipulation tasks. In the work presented here, we address mobile manipulation with humanoids in cluttered environments, particularly the task of collecting objects and delivering them to designated places in a home-like environment while clearing obstacles out of the way. We implemented our system for a Nao humanoid tidying up a room, i.e., the robot has to collect items scattered on the floor, move obstacles out of its way, and deliver the objects to designated target locations. Despite the limited sensing and motion capabilities of the low-cost platform, the experiments show that our approach results in reliable task execution by applying monitoring actions to verify object and robot states.
-
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, 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.
-
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 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.
-
Christian Dornhege, Alexander Kleiner and Andreas Kolling.
Coverage Search in 3D.
In
Proceedings of the Symposium on Safety Security and Rescue Robotics (SSRR).
2013.
(PDF)
(BIB)
-
Andreas Hertle and Christian Dornhege.
Efficient Extensible Path Planning on 3D Terrain Using Behavior Modules.
In
Proceedings of the European Conference on Mobile Robotics (ECMR).
2013.
(PDF)
(BIB)
-
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.
-
Christian Dornhege and Andreas Hertle.
Integrated Symbolic Planning in the Tidyup-Robot Project.
In
AAAI Spring Symposium - Designing Intelligent Robots: Reintegrating AI II.
AAAI Press 2013.
(PDF)
(BIB)
-
Christian Dornhege and Alexander Kleiner.
A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
Advanced Robotics 27 (6). 2013.
(BIB)
-
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.
-
Stefan Kohlbrecher, Karen Petersen, Gerald Steinbauer, Johannes Maurer, Peter Lepej, Suzana Uran, Rodrigo Ventura, Christian Dornhege, Andreas Hertle, Raymond Sheh and Johannes Pellenz.
Community-Driven Development of Standard Software Modules for Search and Rescue Robots.
In
Safety, Security and Rescue Robotics (SSRR).
2012.
-
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.
-
Christian Dornhege and Alexander Kleiner.
A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
In
Proceedings of the IEEE International Symposium on Safety, Security and Rescue Robotics (SSRR).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the problem of an autonomous robot searching for objects in unknown 3d space. Similar to the well known frontier-based exploration in 2d, the problem is to determine a minimal sequence of sensor viewpoints until the entire search space has been explored. We introduce a novel approach that combines the two concepts of voids, which are unexplored volumes in 3d, and frontiers, which are regions on the boundary between voids and explored space. Our approach has been evaluated on a mobile platform equipped with a manipulator searching for victims in a simulated USAR setup. First results indicate the real-world capability and search efficiency of the proposed method.
-
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.
-
R. Kümmerle, B. Steder, Christian Dornhege, Alexander Kleiner, G. Grisetti and W. Burgard.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
Autonomous Robots 30, pp. 25-39. 2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, most existing solutions to the SLAM problem learn the maps from scratch and have no means for incorporating prior information. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. It inserts correspondences found between stereo and three-dimensional range data and the aerial images as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired even in mixed in- and outdoor environments by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency.
-
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.
-
Alexander Kleiner and Christian Dornhege.
Mapping for the Support of First Responders in Critical Domains.
Journal of Intelligent and Robotic Systems (JINT), pp. 1-29. 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In critical domains such as urban search and rescue (USAR), and bomb disposal, the deployment of teleoperated robots is essential to reduce the risk of first responder personnel. Teleoperation is a difficult task, particularly when controlling robots from an isolated safety zone. In general, the operator has to solve simultaneously the problems of mission planning, target identification, robot navigation, and robot control. We introduce a system to support teleoperated navigation with real-time mapping consisting of a two-step scan matching method that re-considers data associations during the search. The algorithm processes data from laser range finder and gyroscope only, thereby it is independent from the robot platform. Furthermore, we introduce a user-guided procedure for improving the global consistency of maps generated by the scan matcher. Globally consistent maps are computed by a graph-based maximum likelihood method that is biased by localizing crucial parts of the scan matcher trajectory on a prior given geo-tiff image. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system was evaluated in a test maze by first responders during the Disaster City event in Texas 2008.
-
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.
-
Alexander Kleiner and Christian Dornhege.
Operator-Assistive Mapping in Harsh Environments.
In
IEEE International Workshop on Safety, Security and Rescue Robotics
(SSRR 2009), pp. 1-6.
2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Teleoperation is a difficult task, particularly when
controlling robots from an isolated operator station.
In general, the operator has to solve nearly blindly the problems of mission
planning, target identification, robot navigation, and robot control at the same time.
The goal of the proposed system is to support teleoperated navigation
with real-time mapping.
We present a novel scan matching technique that re-considers data
associations during the search, enabling robust pose estimation even under
varying roll and pitch angle of the robot enabling mapping
on rough terrain.
The approach has been implemented as an embedded system and extensively tested
on robot platforms designed for teleoperation in critical situations, such as bomb
disposal.
Furthermore,
the system has been evaluated in a test maze by first responders during
the Disaster City event in Texas 2008.
Finally, experiments conducted within different environments show that
the system yields comparably accurate maps in real-time when
compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.
-
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.
-
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.
-
Moritz Göbelbecker and Christian Dornhege.
Realistic Cities in Simulated Environments - An Open Street Map to Robocup Rescue Converter.
In
Online-Proceedings of the Fourth International Workshop on Synthetic Simulation
and Robotics to Mitigate Earthquake Disaster (SRMED 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
A general problem when developing large scale disaster simulation environments is to acquire GIS data.
In this work, we tackle the problem of map generation from public sources.
Usually the major problem is not only the data conversion itself, but to get access to the data at all.
We solve this problem by using the website OpenStreetMap.org, that provides mapping data for the whole world in a wiki-style concept, as our source of data,
thus being able to generate maps for almost any city.
The data is converted to the format required by the Robocup Rescue Simulation System, enabling simulations
on various real-world scenarios.
-
Rainer Kümmerle, Bastian Steder, Christian Dornhege, Michael Ruhnke, Giorgio Grisetti, Cyrill Stachniss and Alexander Kleiner.
On Measuring the Accuracy of SLAM Algorithms.
Autonomous Robots 27 (4), pp. 387-407. 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In this paper, we address the problem of creating an objective benchmark for evaluating SLAM approaches. We propose a framework for analyzing the results of a SLAM approach based on a metric for measuring the error of the corrected trajectory. This metric uses only relative relations between poses and does not rely on a global reference frame. This overcomes serious shortcomings of approaches using a global reference frame to compute the error. Our method furthermore allows us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot.
We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the robotics community. The relations have been obtained by manually matching laser-range observations to avoid the errors caused by matching algorithms. Our benchmark framework allows the user to easily analyze and objectively compare different SLAM approaches.
-
Wolfram Burgard, Cyrill Stachniss, Giorgio Grisetti, Bastian Steder, Rainer Kümmerle, Christian Dornhege, Michael Ruhnke, Alexander Kleiner and Juan D. Tardos.
A Comparison of SLAM Algorithms Based on a Graph of Relations.
In
Proceedings of the 2009 IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS 2009), pp. 2089-2095.
IEEE 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In this paper, we address the problem of creating
an objective benchmark for comparing SLAM approaches.
We propose a framework for analyzing the results of SLAM
approaches based on a metric for measuring the error of the
corrected trajectory. The metric uses only relative relations
between poses and does not rely on a global reference frame.
The idea is related to graph-based SLAM approaches in
the sense that it considers the energy needed to deform the
trajectory estimated by a SLAM approach to the ground
truth trajectory. Our method enables us to compare SLAM
approaches that use different estimation techniques or different
sensor modalities since all computations are made based on the
corrected trajectory of the robot. We provide sets of relative
relations needed to compute our metric for an extensive set
of datasets frequently used in the SLAM community. The
relations have been obtained by manually matching laser-range
observations. We believe that our benchmarking framework
allows the user an easy analysis and objective comparisons
between different SLAM approaches.
-
Rainer Kümmerle, Bastian Steder, Christian Dornhege, Alexander Kleiner, Giorgio Grisetti and Wolfram Burgard.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
In
Proceedings of 2009 Robotics: Science and Systems (RSS 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To effectively navigate in their environments and accurately
reach their target locations, mobile robots require a globally
consistent map of the environment. The problem of learning a map
with a mobile robot has been intensively studied in the past and
is usually referred to as the simultaneous localization and
mapping (SLAM) problem. However, existing solutions to the SLAM
problem typically rely on loop-closures to obtain global
consistency and do not exploit prior information even if it is
available. In this paper, we present a novel SLAM approach that
achieves global consistency by utilizing publicly accessible
aerial photographs as prior information. Our approach inserts
correspondences found between three-dimensional laser range
scans and the aerial image as constraints into a graph-based
formulation of the SLAM problem. We evaluate our algorithm based
on large real-world datasets acquired in a mixed in- and outdoor
environment by comparing the global accuracy with
state-of-the-art SLAM approaches and GPS. The experimental
results demonstrate that the maps acquired with our method show
increased global consistency.
-
Christian Dornhege and Alexander Kleiner.
Fully autonomous planning and obstacle negotiation on rough terrain using behavior maps.
In
Video Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2007).
San Diego, California 2007.
-
Christian Dornhege and Alexander Kleiner.
Behavior maps for online planning of obstacle negotiation and climbing on rough terrain.
In
Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2007), pp. 3005-3011.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as Obstacle Negotiation (ON). In this paper, we introduce a planning framework that extends ON to the general case, where different types of terrain classes directly map to specific robot skills, such as climbing stairs and ramps. This extension is based on a new concept called behavior maps, which is utilized for the planning and execution of complex skills. Behavior maps are directly generated from elevation maps, i.e. two-dimensional grids storing in each cell the corresponding height of the terrain surface, and a set of skill descriptions. Results from extensive experiments are presented, showing that the method enables the robot to explore successfully rough terrain in real-time, while selecting the optimal trajectory in terms of costs for navigation and skill execution.
-
Alexander Kleiner and Christian Dornhege.
Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
Journal of Field Robotics 24, pp. 723-745. 2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Urban Search And Rescue (USAR) is a time critical task. Rescue teams have to explore a large terrain within a short amount of time in order to locate survivors after a disaster. One goal in Rescue Robotics is to have a team of heterogeneous robots that explore autonomously, or partially guided by an incident commander, the disaster area. Their task is to jointly create a map of the terrain and to register victim locations, which can further be utilized by human task forces for rescue. Basically, the robots have to solve autonomously in real-time the problem of Simultaneous Localization and Mapping (SLAM), consisting of a continuous state estimation problem and a discrete data association problem. Extraordinary circumstances after a real disaster make it very hard to apply common techniques. Many of these have been developed under strong assumptions, for example, they require polygonal structures, such as typically found in office-like environments. Furthermore, most techniques are not deployable in real-time. In this paper we propose real-time solutions for localization and mapping, which all have been extensively evaluated within the test arenas of the National Institute of Standards and Technology (NIST). We specifically deal with the problems of vision-based pose tracking on tracked vehicles, the building of globally consistent maps based on a network of RFID tags, and the building of elevation maps from readings of a tilted Laser Range Finder (LRF). Our results show that these methods lead under modest computational requirements to good results within the utilized testing arenas.
-
Alexander Kleiner, Christian Dornhege and Dali Sun.
Mapping disaster areas jointly: RFID -Coordinated SLAM by Humans and Robots.
In
Proceedings of the IEEE International Workshop on Safety, Security
and Rescue Robotics (SSRR 2007), pp. 1-6.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the problem of jointly performing SLAM by humans and robots in Urban Search And Rescue (USAR) scenarios. In this context, SLAM is a challenging task. First, places are hardly re-observable by vision techniques since visibility might be affected by smoke and fire. Second, loop-closure is cumbersome due to the fact that firemen will intentionally try to avoid performing loops when facing the reality of emergency response, e.g.USAR, while they are searching for victims. Furthermore, there might be places that are only accessible to robots, making it necessary to integrate humans and robots into one team for mapping the area after a disaster. In this paper, we introduce a method for jointly correcting individual trajectories of humans and robots by utilizing RFID technology for data association. Hereby the poses of humans and robots are tracked by a PDR (Pedestrian Dead Reckoning), and slippage sensitive odometry, respectively. We conducted extensive experiments with a team of humans, and a human-robot team within a semi-outdoor environment. Results from these experiments show that the introduced method allows to improve single trajectories based on the joint graph, even if they do not contain any loop.
-
Alexander Kleiner, Christian Dornhege, Rainer Kuemmerle, Michael Ruhnke, Bastian Steder, Bernhard Nebel, Patrick Doherty, Mariusz Wzorek, Piotr Rudol, Gianpaolo Conte, S. Durante and D. Lundstrom.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
In
CDROM Proceedings of the International RoboCup Symposium '05.
Bremen, Germany 2006.
(Show abstract)
(Hide abstract)
(PDF)
This paper describes the approach of the RescueRobots Freiburg team,
which 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). Furthermore we introduce linkMAV, a micro aerial
vehicle platform.
Our approach covers RFID-based SLAM and exploration, autonomous detection
of relevant 3D structures, visual odometry, 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.
-
Christian Dornhege and Alexander Kleiner.
Visual Odometry for Tracked Vehicles.
In
Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2006).
2006.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Localization and mapping on autonomous robots typically requires a good pose estimate, which is hard to acquire if the vehicle is tracked. In this paper we describe a solution to the pose estimation problem by utilizing a consumer-quality camera and an Inertial Measurement Unit (IMU). The basic idea is to continuously track salient features with the KLT feature tracker over multiple images taken by the camera and to extract from the tracked features image vectors resulting from the robot's motion. Each image vector is taken for a voting that best explains the robot's motion. Image vectors vote according to a previously trained ^\m2102tile coding^\m2112 classificator that assigns to each possible image vector a translation probability. Our results show that the proposed single camera solution leads to sufficiently accurate pose estimates of the tracked vehicle.
-
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.
-
Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger and Joerg Stueckler.
ResQ Freiburg: Team Description and Evaluation, Team Description Paper, Rescue Simulation League.
In
CDROM Proceedings of the International RoboCup Symposium '04.
Lisbon, Portugal 2004.
(PDF)
-
Thomas Keller and Malte Helmert.
Trial-based Heuristic Tree Search for Finite Horizon MDPs.
In
Proceedings of the 1st Multidisciplinary Conference on Reinforcement Learning and Decision Making
(RLDM 2013), pp. 101-105.
2013.
Extended abstract of the ICAPS 2013 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Dynamic programming is a well-known approach for solving MDPs. In
large state spaces, asynchronous versions like Real-Time Dynamic
Programming (RTDP) have been applied successfully. If unfolded
into equivalent trees, Monte-Carlo Tree Search algorithms are a
valid alternative. UCT, the most popular representative, obtains
good anytime behavior by guiding the search towards promising
areas of the search tree and supporting non-admissible
heuristics. The global Heuristic Search algorithm AO* finds
optimal solutions for MDPs that can be represented as acyclic
AND/OR graphs.
Despite the differences, these approaches actually have much in
common. We present the Trial-based Heuristic Tree Search (THTS)
framework that subsumes these approaches and distinguishes them
based on only five ingredients: heuristic function, backup
function, action selection, outcome selection, and trial
length. We describe the ingredients that model RTDP, AO* and UCT
within this framework, and use THTS to combine attributes of these
algorithms step by step in order to derive novel algorithms with
superior theoretical properties. We merge Full Bellman and
Monte-Carlo backup functions to Partial Bellman backups, and gain
a function that both allows partial updates and a procedure that
labels states when they are solved. DP-UCT combines attributes and
theoretical properties from RTDP and UCT even though it differs
from the latter only in the used Partial Bellman backups. Our main
algorithm, UCT* adds a limited trial length to DP-UCT to inherit
the global search behavior of AO*, which ensures that parts of the
state space that are closer to the root are investigated more
thoroughly. The experimental evaluation shows that both DP-UCT and
UCT* are not only superior to UCT, but also outperform P ROST, the
winner of the International Probabilistic Planning Competition
(IPPC) 2011 on the benchmarks of IPPC 2011.
-
Martin Wehrle, Malte Helmert, Dr. Yusra Alkhazraji and Robert Mattmüller.
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core.
In
Proceedings of the 23rd International Conference on
Automated Planning and Scheduling (ICAPS13).
2013.
(Show abstract)
(Hide abstract)
(PDF)
In the last years, pruning techniques based on partial order reduction have
found increasing attention in the planning community. One recent result is
that the expansion core method is a special case of the strong stubborn sets
method proposed in model checking. However, it is still an open question if
there exist efficiently computable strong stubborn sets with strictly
higher pruning power than expansion core. In this paper, we prove that the
pruning power of strong stubborn sets is strictly higher than the pruning
power of expansion core even for a straight-forward instantiation of strong
stubborn sets. This instantiation is as efficiently computable as expansion
core. Hence, our theoretical results suggest that strong stubborn sets should
be preferred to expansion core. Our empirical evaluation on all optimal
benchmarks from the international planning competitions up to 2011 supports
the theoretical results.
-
Patrick Eyerich and Malte Helmert.
Stronger Abstraction Heuristics Through Perimeter Search.
In
Proceedings of the 23rd International Conference on
Automated Planning and Scheduling (ICAPS13).
2013.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Perimeter search is a bidirectional search algorithm consisting
of two phases. In the first phase, a limited regression search
computes the perimeter, a region which must necessarily
be passed in every solution. In the second phase, a heuristic
forward search finds an optimal plan from the initial state to
the perimeter.
The drawback of perimeter search is the need to compute
heuristic estimates towards every state on the
perimeter in the forward phase. We show that this limitation can
be effectively overcome when using pattern database
(PDB) heuristics in the forward phase.
The combination of perimeter search and PDB heuristics has been
considered previously by Felner and Ofek for solving combinatorial
puzzles. They claimed that, based on theoretical considerations and
experimental evidence, the use of perimeter search in this context
offers "limited or no benefits". Our theoretical and experimental
results show that this assessment should be revisited.
-
Thomas Keller and Malte Helmert.
Trial-based Heuristic Tree Search for Finite Horizon MDPs.
In
Proceedings of the 23rd International Conference on
Automated Planning and Scheduling (ICAPS 2013), pp. 135-143.
2013.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Dynamic programming is a well-known approach for solving
MDPs. In large state spaces, asynchronous versions like
Real-Time Dynamic Programming have been applied successfully. If
unfolded into equivalent trees, Monte-Carlo Tree Search
algorithms are a valid alternative. UCT, the most popular
representative, obtains good anytime behavior by guiding the
search towards promising areas of the search tree. The Heuristic
Search algorithm AO∗ finds optimal solutions for MDPs that can
be represented as acyclic AND/OR graphs.
We introduce a common framework, Trial-based Heuristic Tree
Search, that subsumes these approaches and distinguishes them
based on five ingredients: heuristic function, backup function,
action selection, outcome selection, and trial length. Using
this framework, we describe three new algorithms which mix these
ingredients in novel ways in an attempt to combine their
different strengths. Our evaluation shows that two of our
algorithms not only provide superior theoretical properties to
UCT, but also outperform state-of-the-art approaches
experimentally.
-
Dr. Yusra Alkhazraji, Martin Wehrle, Robert Mattmüller and Malte Helmert.
A Stubborn Set Algorithm for Optimal Planning.
In
Proceedings of the 20th European Conference on
Artificial Intelligence (ECAI 2012).
2012.
(Show abstract)
(Hide abstract)
(PDF)
We adapt a partial order reduction technique based on stubborn
sets, originally proposed for detecting dead ends in Petri Nets,
to the setting of optimal planning. We demonstrate that stubborn
sets can provide significant state space reductions on standard
planning benchmarks, outperforming the expansion core method.
-
Silvan Sievers, Manuela Ortlieb and Malte Helmert.
Efficient Implementation of Pattern Database Heuristics for Classical Planning.
In
Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012), pp. 105-111.
AAAI Press 2012.
(Show abstract)
(Hide abstract)
(PDF)
Despite their general success in the heuristic search community, pattern database (PDB)
heuristics have, until very recently, not been used by the most successful classical
planning systems.
We describe a new efficient implementation of pattern database heuristics within the
Fast Downward planner. A planning system using this implementation is competitive with
the state of the art in optimal planning, significantly improving over results from
the previous best PDB heuristic implementation in planning.
-
Raz Nissim, Jörg Hoffmann and Malte Helmert.
Computing Perfect Heuristics in Polynomial Time:
On Bisimulation and Merge-and-Shrink Abstractions in Optimal
Planning.
In
Proceedings of the
Twenty-Second
International Joint Conference on Artificial Intelligence
(IJCAI 2011), pp. 1983-1990.
2011.
Erratum: In Section 7, we introduce greedy bisimulation
as only respecting the bisimulation property for transitions
(s, l, s') where sd(s) <= sd(s'). The implementation
we evaluate in Section 8 is actually even more greedy than that,
only respecting transitions where sd(s) < sd(s').
Using the definition from Section 7 leads to a strategy that
behaves very similarly to the strategies using regular (non-greedy)
bisimulation on these benchmarks..
(Show abstract)
(Hide abstract)
(PDF)
A* with admissible heuristics is a very successful approach to
optimal planning. But how to derive such heuristics
automatically? Merge-and-shrink abstraction (M&S) is a
general approach to heuristic design whose key advantage is
its capability to make very fine-grained choices in defining
abstractions. However, little is known about how to actually
make these choices. We address this via the well-known notion
of bisimulation. When aggregating only bisimilar
states, M&s yields a perfect heuristic. Alas,
bisimulations are exponentially large even in trivial
domains. We show how to apply label reduction -- not
distinguishing between certain groups of operators -- without
incurring any information loss, while potentially reducing
bisimulation size exponentially. In several benchmark domains,
the resulting algorithm computes perfect heuristics in
polynomial time. Empirically, we show that approximating
variants of this algorithm improve the state of the art in
M&S heuristics. In particular, a hybrid of two such
variants is competitive with the leading heuristic LM-cut.
-
Carmel Domshlak, Malte Helmert, Erez Karpas, Emil Keyder, Silvia Richter, Gabriele Röger, Jendrik Seipp and Matthias Westphal.
BJOLP: The Big Joint Optimal Landmarks Planner
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 91-95.
2011.
(Show abstract)
(Hide abstract)
(PDF)
BJOLP, The Big Joint Optimal Landmarks Planner uses landmarks
to derive an admissible heuristic, which is then used to guide
a search for a cost-optimal plan. In this paper we review
landmarks and describe how they can be used to derive an
admissible heuristic. We conclude with presenting the BJOLP
planner.
-
Silvia Richter, Matthias Westphal and Malte Helmert.
LAMA 2008 and 2011 (planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 50-54.
2011.
(Show abstract)
(Hide abstract)
(PDF)
LAMA is a propositional planning system based on heuristic
search with landmarks. This paper describes two versions of
LAMA that were entered into the 2011 International Planning
Competition: the original LAMA as developed for the 2008
competition and a new re-implementation of LAMA that uses the
latest version of the Fast Downward Planning Framework.
Landmarks are propositions that must be true in every solution
of a planning task. LAMA uses a heuristic derived from
landmarks in conjunction with the well-known FF
heuristic. LAMA builds on the Fast Downward Planning System
using non-binary (but finite domain) state variables and
multi-heuristic search. A weighted A* search is used with
iteratively decreasing weights, so that the planner continues
to search for plans of better quality until the search is
terminated. LAMA combines cost-to-goal and distance-to-goal
estimates with the aim of finding good solutions using
reasonable runtime.
-
Malte Helmert and Carmel Domshlak.
LM-Cut: Optimal Planning with the Landmark-Cut Heuristic
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 103-105.
2011.
(Show abstract)
(Hide abstract)
(PDF)
The LM-Cut planner uses the landmark-cut heuristic, introduced
by the authors in 2009, within a standard A* progression
search framework to find optimal sequential plans for
STRIPS-style planning tasks. This short paper recapitulates
the main ideas surrounding the landmark-cut heuristic and
provides pointers for further reading.
-
Raz Nissim, Jörg Hoffmann and Malte Helmert.
The Merge-and-Shrink Planner: Bisimulation-based
Abstraction for Optimal Planning (planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 106-107.
2011.
(Show abstract)
(Hide abstract)
(PDF)
Merge-and-shrink abstraction is a general approach to
heuristic design whose key advantage is its capability to make
very fine-grained choices in defining abstractions. The
Merge-and-shrink planner uses two different strategies for
making these choices, both based on the well-known notion of
bisimulation. The resulting heuristics are used in two
sequential runs of A* search.
-
Carmel Domshlak, Malte Helmert, Erez Karpas and Shaul Markovitch.
The SelMax Planner: Online Learning for Speeding up Optimal
Planning (planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 108-112.
2011.
(Show abstract)
(Hide abstract)
(PDF)
The SelMax planner combines two state-of-the-art admissible
heuristics using an online learning approach. In this paper we
describe the online learning approach employed by SelMax,
briefly review the Fast Downward framework, and describe the
SelMax planner.
-
Malte Helmert, Gabriele Röger, Jendrik Seipp, Erez Karpas, Jörg Hoffmann, Emil Keyder, Raz Nissim, Silvia Richter and Matthias Westphal.
Fast Downward Stone Soup (planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 38-45.
2011.
(Show abstract)
(Hide abstract)
(PDF)
Fast Downward Stone Soup is a sequential portfolio planner
that uses various heuristics and search algorithms that have
been implemented in the Fast Downward planning system.
We present a simple general method for concocting "planner
soups", sequential portfolios of planning algorithms, and
describe the actual recipes used for Fast Downward Stone Soup
in the sequential optimization and sequential satisficing
tracks of IPC 2011.
-
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger and Jendrik Seipp.
FD-Autotune: Automated Configuration of Fast Downward
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 31-37.
2011.
(Show abstract)
(Hide abstract)
(PDF)
The FD-Autotune submissions for the IPC-2011 sequential tracks
consist of three instantiations of the latest, highly
parametric version of the Fast Downward Planning
Framework. These instantiations have been automatically
configured for performance on a wide range of planning
domains, using the well-known ParamILS configurator. Two of
the instantiations were entered into the sequential
satisficing track and one into the sequential optimising
track. We describe how the extremely large configuration space
of Fast Downward was restricted to a subspace that, although
still very large, can be managed by state-of-the-art automated
configuration procedures, and how ParamILS was then used to
obtain performance-optimised configurations.
-
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger and Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Planning and
Learning Part.
2011.
(Show abstract)
(Hide abstract)
(PDF)
The FD-Autotune learning planning system is based on the idea
of domain-specific configuration of the latest, highly
parametric version of the Fast Downward Planning Framework by
means of a generic automated algorithm configuration
procedure. We describe how the extremely large configuration
space of Fast Downward was restricted to a subspace that,
although still very large, can be managed by state-of-the-art
automated configuration procedures. FD-Autotune uses the
well-known ParamILS configurator and was realised using the
recently developed HAL experimentation environment.
-
Malte Helmert, Gabriele Röger and Erez Karpas.
Fast Downward Stone Soup: A Baseline for Building Planner Portfolios.
In
Proceedings of the ICAPS-2011
Workshop on Planning and Learning (PAL), pp. 28-35.
2011.
(Show abstract)
(Hide abstract)
(PDF)
Fast Downward Stone Soup is a sequential portfolio planner that
uses various heuristics and search algorithms that
have been implemented in the Fast Downward planning system.
We present a simple general method for concocting "planner
soups", sequential portfolios of planning algorithms, and
describe the actual recipes used for Fast Downward Stone Soup
in the sequential optimization and sequential satisficing
tracks of IPC 2011.
This paper is, first and foremost, a planner description.
Fast Downward Stone Soup was entered into the sequential
(non-learning) tracks of IPC 2011. Due to time constraints, we
did not enter it into the learning competition at IPC
2011. However, we believe that the approach might still be of
interest to the planning and learning community, as it
represents a baseline against which other, more sophisticated
portfolio learners can be usefully compared.
-
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger and Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward.
In
Proceedings of the ICAPS-2011
Workshop on Planning and Learning (PAL), pp. 13-20.
2011.
(Show abstract)
(Hide abstract)
(PDF)
In this work, we present the FD-Autotune learning planning
system, which is based on the idea of domain-specific
configuration of the latest, highly parametric version of the
Fast Downward Planning Framework by means of a generic
automated algorithm configuration procedure. We describe how
the extremely large configuration space of Fast Downward was
restricted to a subspace that, although still very large, can
be managed by a state-of-the-art automated configuration
procedure. Additionally, we give preliminary results obtained
from applying our approach to the nine domains of the IPC-2011
learning track, using the well-known ParamILS configurator
and the recently developed HAL experimentation environment.
-
Raz Nissim, Jörg Hoffmann and Malte Helmert.
Computing Perfect Heuristics in Polynomial Time:
On Bisimulation and Merge-and-Shrink Abstractions in Optimal
Planning.
In
Proceedings of the ICAPS-2011
Workshop on Heuristics for Domain-independent Planning (HDIP), pp. 5-13.
2011.
Superseded by the IJCAI 2011 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
A* with admissible heuristics is a very successful approach to
optimal planning. But how to derive such heuristics
automatically? Merge-and-shrink abstraction (M&S) is a
general approach to heuristic design whose key advantage is
its capability to make very fine-grained choices in defining
abstractions. However, little is known about how to actually
make these choices. We address this via the well-known notion
of bisimulation. When aggregating only bisimilar
states, M&s yields a perfect heuristic. Alas,
bisimulations are exponentially large even in trivial
domains. We show how to apply label reduction -- not
distinguishing between certain groups of operators -- without
incurring any information loss, while potentially reducing
bisimulation size exponentially. In several benchmark domains,
the resulting algorithm computes perfect heuristics in
polynomial time. Empirically, we show that approximating
variants of this algorithm improve the state of the art in
M&S heuristics. In particular, a hybrid of two such
variants is competitive with the leading heuristic LM-cut.
-
Jendrik Seipp and Malte Helmert.
Fluent Merging for Classical Planning Problems.
In
Proceedings of the ICAPS-2011
Workshop on Knowledge Engineering for Planning and Scheduling (KEPS), pp. 47-53.
2011.
Note: This version of the paper fixes two mistakes
(in Def. 2 and in the text after Def. 3) that are present in the
version of the paper that is linked from the workshop
webpage..
(Show abstract)
(Hide abstract)
(PDF)
Fluent merging is a reformulation technique for classical
planning problems that can be applied automatically or
semi-automatically. The reformulation strives to transform a
planning task into a representation that allows a planning
algorithm to find solutions more efficiently or to find
solutions of better quality. This work introduces different
approaches for fluent merging and evaluates them within a
state-of-the-art planning system.
-
Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp and Malte Helmert (eds.).
Proceedings of the
21st International
Conference on Automated Planning and Scheduling (ICAPS 2011).
AAAI Press, Menlo Park, California, USA 2011.
-
Malte Helmert and Gabriele Röger.
Relative-Order Abstractions for the Pancake Problem.
In
Helder Coelho, Rudi Studer and Michael Wooldridge (eds.),
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), pp. 745-750.
IOS Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
The pancake problem is a famous search problem where the
objective is to sort a sequence of objects (pancakes)
through a minimal number of prefix reversals
(flips). The best approaches for the problem are based
on heuristic search with abstraction (pattern database)
heuristics. We present a new class of abstractions for the
pancake problem called relative-order abstractions.
Relative-order abstractions have three advantages over the
object-location abstractions considered in previous
work. First, they are size-independent, i.e., do not
need to be tailored to a particular instance size of the
pancake problem. Second, they are more compact in that
they can represent a larger number of pancakes within
abstractions of bounded size. Finally, they can exploit
symmetries in the problem specification to allow
multiple heuristic lookups, significantly improving search
performance over a single lookup. Our experiments show that
compared to object-location abstractions, our new techniques
lead to an improvement of one order of magnitude in runtime
and up to three orders of magnitude in the number of generated
states.
-
Blai Bonet and Malte Helmert.
Strengthening Landmark Heuristics via Hitting Sets.
In
Helder Coelho, Rudi Studer and Michael Wooldridge (eds.),
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), pp. 329-334.
IOS Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(technical report with proofs; PDF)
(slides of Blai's ECAI 2010 presentation; PDF)
(slides of Malte's SS 2010 group seminar presentation; PDF)
The landmark cut heuristic is perhaps the strongest known
polytime admissible approximation of the optimal delete
relaxation heuristic h+. Equipped with
this heuristic, a best-first search was able to optimally
solve 40% more benchmark problems than the winners of the
sequential optimization track of IPC 2008. We show that this
heuristic can be understood as a simple relaxation of a
hitting set problem, and that stronger heuristics can be
obtained by considering stronger relaxations. Based on
these findings, we propose a simple polytime method for
obtaining heuristics stronger than landmark cut, and
evaluate them over benchmark problems. We also show that
hitting sets can be used to characterize
h+ and thus provide a fresh and novel
insight for better comprehension of the delete relaxation.
-
Emil Keyder, Silvia Richter and Malte Helmert.
Sound and Complete Landmarks for And/Or Graphs.
In
Helder Coelho, Rudi Studer and Michael Wooldridge (eds.),
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), pp. 335-340.
IOS Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
Landmarks for a planning problem are subgoals that are
necessarily made true at some point in the execution of any
plan. Since verifying that a fact is a landmark is
PSPACE-complete, earlier approaches have focused on finding
landmarks for the delete relaxation Π+.
Furthermore, some of these approaches have approximated
this set of landmarks, although it has been shown that the
complete set of causal delete-relaxation landmarks can
be identified in polynomial time by a simple procedure over
the relaxed planning graph. Here, we give a declarative
characterisation of this set of landmarks and show that the
procedure computes the landmarks described by our
characterisation. Building on this, we observe that the
procedure can be applied to any delete-relaxation problem and
take advantage of a recent compilation of the
m-relaxation of a problem into a problem with no delete
effects to extract landmarks that take into account delete
effects in the original problem. We demonstrate that this
approach finds strictly more causal landmarks than previous
approaches and discuss the relationship between increased
computational effort and experimental performance, using these
landmarks in a recently proposed admissible landmark-counting
heuristic.
-
Malte Helmert.
Lessons Learned from Benchmarking in the Automated Planning
Community.
In
Proceedings of the
ECAI 2010
Workshop on Benchmarking Intelligent (Multi-) Robot Systems.
2010.
(PDF)
-
Patrick Eyerich, Thomas Keller and Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem.
In
Maria Fox and David Poole (eds.),
Proceedings of the Twenty-Fourth AAAI Conference on Artificial
Intelligence (AAAI
2010), pp. 51-58.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the stochastic variant of the Canadian
Traveler's Problem, a path planning problem where adverse
weather can cause some roads to be untraversable. The agent
does not initially know which roads can be used. However, it
knows a probability distribution for the weather, and it can
observe the status of roads incident to its location. The
objective is to find a policy with low expected travel cost.
We introduce and compare several algorithms for the
stochastic CTP. Unlike the optimistic approach most
commonly considered in the literature, the new approaches we
propose take uncertainty into account explicitly. We show
that this property enables them to generate policies of much
higher quality than the optimistic one, both theoretically
and experimentally.
-
Patrick Eyerich, Thomas Keller and Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem
(Extended Abstract).
In
Ariel Felner and Nathan Sturtevant (eds.),
Proceedings of the Third Annual Symposium on Combinatorial
Search (SoCS 2010), pp. 147-148.
AAAI Press 2010.
Extended abstract of the AAAI paper by the same name.
(PDF)
-
Malte Helmert.
Landmark Heuristics for the Pancake Problem.
In
Ariel Felner and Nathan Sturtevant (eds.),
Proceedings of the Third Annual Symposium on Combinatorial
Search (SoCS 2010), pp. 109-110.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
We describe the gap heuristic for the pancake problem,
which dramatically outperforms current abstraction-based
heuristics for this problem. The gap heuristic belongs to a
family of landmark heuristics that have recently been
very successfully applied to planning problems.
-
Malte Helmert and Hauke Lasinger.
The Scanalyzer Domain: Greenhouse Logistics as a Planning Problem.
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. 234-237.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
We introduce the Scanalyzer planning domain, a domain for
classical planning which models the problem of automatic
greenhouse logistic management.
At its mathematical core, the Scanalyzer domain is a
permutation problem with striking similarities to common
search benchmarks such as Rubik's Cube or TopSpin. At the same
time, it is also a real application domain, and efficient
algorithms for the problem are of considerable practical
interest.
The Scanalyzer domain was used as a benchmark for sequential
planners at the last International Planning Competition. The
competition results show that domain-independent automated
planners can find solutions of comparable quality to those
generated by specialized algorithms developed by domain
experts, while being considerably more flexible.
-
Robert Mattmüller, Manuela Ortlieb, Malte Helmert and Pascal Bercher.
Pattern Database Heuristics for Fully Observable Nondeterministic Planning.
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. 105-112.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(BIB)
When planning in an uncertain environment, one is often
interested in finding a contingent plan that prescribes
appropriate actions for all possible states that may be
encountered during the execution of the plan. We consider the
problem of finding strong and strong cyclic plans for fully
observable nondeterministic (FOND) planning problems. The
algorithm we choose is LAO*, an informed explicit state search
algorithm. We investigate the use of pattern database (PDB)
heuristics to guide LAO* towards goal states. To obtain a
fully domain-independent planning system, we use an automatic
pattern selection procedure that performs local search in the
space of pattern collections. The evaluation of our system on
the FOND benchmarks of the Uncertainty Part of the
International Planning Competition 2008 shows that our
approach is competitive with symbolic regression search in
terms of problem coverage and speed.
-
Gabriele Röger and Malte Helmert.
The More, the Merrier: Combining Heuristic Estimators for
Satisficing Planning.
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. 246-249.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(technical report; PDF)
We empirically examine several ways of exploiting the
information of multiple heuristics in a satisficing best-first
search algorithm, comparing their performance in terms of
coverage, plan quality, speed, and search guidance. Our
results indicate that using multiple heuristics for
satisficing search is indeed useful. Among the combination
methods we consider, the best results are obtained by the
alternation method of the "Fast Diagonally Downward"
planner.
-
Patrick Eyerich, Thomas Keller and Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem.
In
Proceedings of the
ICAPS-2010
Workshop on Planning and Scheduling Under Uncertainty.
2010.
Superseded by the AAAI 2010 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the stochastic variant of the Canadian
Traveler's Problem, a path planning problem where adverse
weather can cause some roads to be untraversable. The agent
does not initially know which roads can be used. However, it
knows a probability distribution for the weather, and it can
observe the status of roads incident to its location. The
objective is to find a policy with low expected travel cost.
We introduce and compare several algorithms for the
stochastic CTP. Unlike the optimistic approach most
commonly considered in the literature, the new approaches we
propose take uncertainty into account explicitly. We show
that this property enables them to generate policies of much
higher quality than the optimistic one, both theoretically
and experimentally.
-
Dunbo Cai, Jörg Hoffmann and Malte Helmert.
Enhancing the Context-Enhanced Additive Heuristic with Precedence Constraints.
In
Proceedings of the 19th International Conference on Automated
Planning and Scheduling (ICAPS 2009), pp. 50-57.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(PDF)
Recently, Helmert and Geffner proposed the context-enhanced
additive heuristic, where fact costs are evaluated relative to
context states that arise from achieving first a pivot
condition of each operator. As Helmert and Geffner pointed
out, the method can be generalized to consider contexts
arising from arbitrary precedence constraints over operator
conditions instead. Herein, we provide such a
generalization. We extend Helmert and Geffner's equations, and
discuss a number of design choices that arise. Drawing on
previous work on goal orderings, we design a family of methods
for automatically generating precedence constraints. We run
large-scale experiments, showing that the technique can help
significantly, depending on the choice of precedence
constraints. We shed some light on this by profiling the
behavior of all possible precedence constraints, using a
sampling technique.
-
Malte Helmert and Carmel Domshlak.
Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?
In
Proceedings of the 19th International Conference on Automated
Planning and Scheduling (ICAPS 2009), pp. 162-169.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(PDF)
(Dagstuhl abstract; PDF)
Current heuristic estimators for classical domain-independent
planning are usually based on one of four ideas: delete
relaxations, critical paths, abstractions,
and, most recently, landmarks. Previously, these
different ideas for deriving heuristic functions were largely
unconnected.
We prove that admissible heuristics based on these ideas are
in fact very closely related. Exploiting this relationship, we
introduce a new admissible heuristic called the landmark
cut heuristic, which compares favourably with the state of
the art in terms of heuristic accuracy and overall
performance.
-
Silvia Richter and Malte Helmert.
Preferred Operators and Deferred Evaluation in Satisficing Planning.
In
Proceedings of the 19th International Conference on Automated
Planning and Scheduling (ICAPS 2009), pp. 273-280.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(PDF)
Heuristic forward search is the dominant approach to
satisficing planning to date. Most successful planning
systems, however, go beyond plain heuristic search by
employing various search-enhancement techniques. One example
is the use of helpful actions or preferred operators,
providing information which may complement heuristic values.
A second example is deferred heuristic evaluation, a search
variant which can reduce the number of costly node
evaluations. Despite the wide-spread use of these
search-enhancement techniques however, we note that few
results have been published examining their usefulness. In
particular, while various ways of using, and possibly
combining, these techniques are conceivable, no work to date
has studied the performance of such variations. In this
paper, we address this gap by examining the use of preferred
operators and deferred evaluation in a variety of settings
within best-first search. In particular, our findings are
consistent with and help explain the good performance of the
winners of the satisficing tracks at IPC 2004 and 2008.
-
Christoph Betz and Malte Helmert.
Planning with h+ in Theory and Practice.
In
Proceedings of the
2nd
Workshop on Heuristics for Domain-independent Planning
at ICAPS 2009.
2009.
(Show abstract)
(Hide abstract)
(PDF)
Many heuristic estimators for classical planning are based on
the so-called delete relaxation, which ignores negative
effects of planning operators. Ideally, such heuristics would
compute the actual goal distance in the delete relaxation,
i.e., the cost of an optimal relaxed plan, denoted by
h+. However, current delete relaxation heuristics only provide
(often inadmissible) estimates to h+ because computing the
correct value is an NP-hard problem.
In this work, we consider the approach of planning with the
actual h+ heuristic from a theoretical and computational
perspective. In particular, we provide domain-dependent
complexity results that classify some standard benchmark
domains into ones where h+ can be computed efficiently and
ones where computing h+ is NP-hard. Moreover, we study
domain-dependent implementations of h+ which show that
the h+ heuristic provides very informative heuristic estimates
compared to other state-of-the-art heuristics.
-
Gabriele Röger and Malte Helmert.
Combining Heuristic Estimators for Satisficing Planning.
In
Proceedings of the
2nd
Workshop on Heuristics for Domain-independent Planning
at ICAPS 2009.
2009.
(Show abstract)
(Hide abstract)
(PDF)
The problem of effectively combining multiple heuristic
estimators has been studied extensively in the context of
optimal planning, but not in the context of satisficing
planning. To narrow this gap, we empirically examine several
ways of exploiting the information of multiple heuristics in a
satisficing best-first search algorithm, comparing their
performance in terms of coverage, plan quality and
runtime. Our empirical results indicate that using multiple
heuristics for satisficing search is indeed useful and that
the best results are not obtained by the most obvious
combination methods.
-
Christoph Betz and Malte Helmert.
Planning with h+ in Theory and Practice.
In
Bärbel Mertsching, Marcus Hund and Zaheer Aziz (eds.),
Proceedings of the 32nd Annual German Conference on Artificial
Intelligence (KI 2009), pp. 9-16.
Springer-Verlag 2009.
(Show abstract)
(Hide abstract)
(PDF)
Many heuristic estimators for classical planning are based on
the so-called delete relaxation, which ignores negative
effects of planning operators. Ideally, such heuristics would
compute the actual goal distance in the delete relaxation,
i.e., the cost of an optimal relaxed plan, denoted by
h+. However, current delete relaxation heuristics only provide
(often inadmissible) estimates to h+ because computing the
correct value is an NP-hard problem.
In this work, we consider the approach of planning with the
actual h+ heuristic from a theoretical and computational
perspective. In particular, we provide domain-dependent
complexity results that classify some standard benchmark
domains into ones where h+ can be computed efficiently and
ones where computing h+ is NP-hard. Moreover, we study
domain-dependent implementations of h+ which show that
the h+ heuristic provides very informative heuristic estimates
compared to other state-of-the-art heuristics.
-
Martin Wehrle and Malte Helmert.
The Causal Graph Revisited for Directed Model
Checking.
In
Jens Palsberg and Zhendong Su (eds.),
Proceedings of the 16th International Static Analysis Symposium
(SAS 2009), pp. 86-101.
Springer-Verlag 2009.
(Show abstract)
(Hide abstract)
(PDF)
(Dagstuhl abstract; PDF)
Directed model checking is a well-established technique to
tackle the state explosion problem when the aim is to find
error states in large systems. In this approach, the state
space traversal is guided through a function that estimates
the distance to nearest error states. States with lower
estimates are preferably expanded during the
search. Obviously, the challenge is to develop distance
functions that are efficiently computable on the one hand and
as informative as possible on the other hand. In this paper,
we introduce the causal graph structure to the context
of directed model checking. Based on causal graph analysis, we
first adapt a distance estimation function from AI planning to
directed model checking. Furthermore, we investigate an
abstraction that is guaranteed to preserve error states. The
experimental evaluation shows the practical potential of these
techniques.
-
Malte Helmert.
Research Statement: Heuristic Search for Domain-Independent
Planning.
In
2nd International Symposium on Combinatorial Search
(SoCS
2009).
2009.
(PDF)
-
Jörg Hoffmann, Piergiorgio Bertoli, Malte Helmert and Marco Pistore.
Message-Based Web Service Composition, Integrity
Constraints, and Planning under Uncertainty: A New
Connection.
Journal of Artificial Intelligence Research 35, pp. 49-117. 2009.
(Show abstract)
(Hide abstract)
(PDF)
Thanks to recent advances, AI Planning has become the
underlying technique for several applications. Figuring
prominently among these is automated Web Service Composition
(WSC) at the "capability" level, where services are
described in terms of preconditions and effects over
ontological concepts. A key issue in addressing WSC as
planning is that ontologies are not only formal vocabularies;
they also axiomatize the possible relationships between
concepts. Such axioms correspond to what has been termed
"integrity constraints" in the actions and change
literature, and applying a web service is essentially a belief
update operation. The reasoning required for belief update is
known to be harder than reasoning in the ontology itself. The
support for belief update is severely limited in current
planning tools.
Our first contribution consists in identifying an interesting
special case of WSC which is both significant and more
tractable. The special case, which we term forward
effects, is characterized by the fact that every
ramification of a web service application involves at least
one new constant generated as output by the web service. We
show that, in this setting, the reasoning required for belief
update simplifies to standard reasoning in the ontology
itself. This relates to, and extends, current notions of
"message-based" WSC, where the need for belief update is
removed by a strong (often implicit or informal) assumption of
"locality" of the individual messages. We clarify the
computational properties of the forward effects case, and
point out a strong relation to standard notions of planning
under uncertainty, suggesting that effective tools for the
latter can be successfully adapted to address the former.
Furthermore, we identify a significant sub-case, named
strictly forward effects, where an actual compilation
into planning under uncertainty exists. This enables us to
exploit off-the-shelf planning tools to solve message-based
WSC in a general form that involves powerful ontologies, and
requires reasoning about partial matches between concepts. We
provide empirical evidence that this approach may be quite
effective, using Conformant-FF as the underlying planner.
-
Malte Helmert.
Concise finite-domain representations for PDDL planning
tasks.
Artificial Intelligence 173, pp. 503-535. 2009.
(Show abstract)
(Hide abstract)
(PDF)
We introduce an efficient method for translating planning
tasks specified in the standard PDDL formalism into a concise
grounded representation that uses finite-domain state
variables instead of the straight-forward propositional
encoding.
Translation is performed in four stages. Firstly, we transform
the input task into an equivalent normal form expressed in a
restricted fragment of PDDL. Secondly, we synthesize
invariants of the planning task that identify groups of
mutually exclusive propositions which can be represented by a
single finite-domain variable. Thirdly, we perform an
efficient relaxed reachability analysis using logic
programming techniques to obtain a grounded representation of
the input. Finally, we combine the results of the third and
fourth stage to generate the final grounded finite-domain
representation.
The presented approach has originally been implemented as part
of the Fast Downward planning system for the 4th International
Planning Competition (IPC4). Since then, it has been used in a
number of other contexts with considerable success, and the
use of concise finite-domain representations has become a
common feature of state-of-the-art planners.
-
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.
-
Malte Helmert and Héctor Geffner.
Unifying the Causal Graph and Additive Heuristics.
In
Proceedings of the 18th International Conference on Automated
Planning and Scheduling (ICAPS 2008), pp. 140-147.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
Many current heuristics for domain-independent planning, such
as Bonet and Geffner's additive heuristic and Hoffmann
and Nebel's FF heuristic, are based on delete
relaxations. They estimate the goal distance of a search state
by approximating the solution cost in a relaxed task where
negative consequences of operator applications are
ignored. Helmert's causal graph heuristic, on the other
hand, approximates goal distances by solving a hierarchy of
"local" planning problems that only involve a single state
variable and the variables it depends on directly.
Superficially, the causal graph heuristic appears quite
unrelated to heuristics based on delete relaxation. In this
contribution, we show that the opposite is true. Using a
novel, declarative formulation of the causal graph heuristic,
we show that the causal graph heuristic is the additive
heuristic plus context. Unlike the original heuristic, our
formulation does not require the causal graph to be acyclic,
and thus leads to a proper generalization of both the causal
graph and additive heuristics. Empirical results show that the
new heuristic is significantly better informed than both
Helmert's original causal graph heuristic and the additive
heuristic and outperforms them across a wide range of standard
benchmarks.
-
Malte Helmert, Patrik Haslum and Jörg Hoffmann.
Explicit-State Abstraction: A New Method for Generating
Heuristic Functions.
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI
2008), pp. 1547-1550.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Many AI problems can be recast as finding an optimal path in a
discrete state space. An abstraction defines an admissible
heuristic function as the distances in a smaller state space
where arbitrary sets of states are "aggregated" into single
states. A special case are pattern database (PDB) heuristics,
which aggregate states iff they agree on the state variables
inside the pattern. Explicit-state abstraction is more flexible,
explicitly aggregating selected pairs of states in a process
that interleaves composition of abstractions with abstraction of
the composites. The increased flexibility gains expressive
power: sometimes, the real cost function can be represented
concisely as an explicit-state abstraction, but not as a
PDB. Explicit-state abstraction has been applied to planning and
model checking, with highly promising empirical results.
-
Malte Helmert and Gabriele Röger.
How Good is Almost Perfect?
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI 2008), pp. 944-949.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Heuristic search using algorithms such as A* and IDA* is the
prevalent method for obtaining optimal sequential solutions for
classical planning tasks. Theoretical analyses of these
classical search algorithms, such as the well-known results of
Pohl, Gaschnig and Pearl, suggest that such heuristic search
algorithms can obtain better than exponential scaling behaviour,
provided that the heuristics are accurate enough.
Here, we show that for a number of common planning benchmark
domains, including ones that admit optimal solution in
polynomial time, general search algorithms such as A* must
necessarily explore an exponential number of search
nodes even under the optimistic assumption of almost
perfect heuristic estimators, whose heuristic error is
bounded by a small additive constant.
Our results shed some light on the comparatively bad performance
of optimal heuristic search approaches in "simple" domains such
as GRIPPER. They suggest that in many domains, further
improvements in run-time require changes to other parts of the
planning algorithm than the heuristic estimator.
-
Malte Helmert and Robert Mattmüller.
Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI 2008), pp. 938-943.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(BIB)
The efficiency of optimal planning algorithms based on heuristic
search crucially depends on the accuracy of the heuristic
function used to guide the search. Often, we are interested in
domain-independent heuristics for planning. In order to assess the
limitations of domain-independent heuristic planning, it appears
interesting to analyse the (in)accuracy of common
domain-independent planning heuristics in the IPC benchmark
domains. For a selection of these domains, we analytically
investigate the accuracy of the h+
heuristic, the hm family of heuristics, and
certain (additive) pattern database heuristics, compared to the
perfect heuristic h*. Whereas
h+ and additive pattern database heuristics
usually return cost estimates proportional to the true cost,
non-additive hm and non-additive
pattern-database heuristics can yield results underestimating
the true cost by arbitrarily large factors.
-
Silvia Richter, Malte Helmert and Matthias Westphal.
Landmarks Revisited.
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI 2008), pp. 975-982.
AAAI Press 2008.
Note: After publication, we found a bug in our implementation
that affects the results in the columns "CG heuristic/local" and
"blind heuristic/local" of Table 1. The version of the paper available
for download here corrects these errors.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Landmarks for propositional planning tasks are variable
assignments that must occur at some point in every solution
plan. We propose a novel approach for using landmarks in
planning by deriving a pseudo-heuristic and combining it with
other heuristics in a search framework. The incorporation of
landmark information is shown to improve success rates and
solution qualities of a heuristic planner. We furthermore show
how additional landmarks and orderings can be found using the
information present in multi-valued state variable
representations of planning tasks. Compared to previously
published approaches, our landmark extraction algorithm provides
stronger guarantees of correctness for the generated landmark
orderings, and our novel use of landmarks during search solves
more planning tasks and delivers considerably better solutions.
-
Malte Helmert.
Understanding Planning Tasks: Domain Complexity and Heuristic
Decomposition.
Volume 4929 of Lecture Notes in Artificial Intelligence.
Springer-Verlag, Heidelberg 2008.
(Springer Online)
-
Malte Helmert, Patrik Haslum and Jörg Hoffmann.
Flexible Abstraction Heuristics for Optimal Sequential
Planning.
In
Proceedings of the Seventeenth International Conference
on Automated Planning and Scheduling (ICAPS 2007), pp. 176-183.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
We describe an approach to deriving consistent heuristics for
automated planning, based on explicit search in abstract state
spaces. The key to managing complexity is interleaving
composition of abstractions over different sets of state
variables with abstraction of the partial composites.
The approach is very general and can be instantiated in many
different ways by following different abstraction
strategies. In particular, the technique subsumes
planning with pattern databases as a special case.
Moreover, with suitable abstraction strategies it is possible to
derive perfect heuristics in a number of classical benchmark
domains, thus allowing their optimal solution in polynomial
time.
To evaluate the practical usefulness of the approach, we perform
empirical experiments with one particular abstraction strategy.
Our results show that the approach is competitive with the state
of the art.
-
Malte Helmert and Gabriele Röger.
How Good is Almost Perfect?
In
Proceedings of the
ICAPS-2007
Workshop on Heuristics for Domain-independent Planning: Progress,
Ideas, Limitations, Challenges.
2007.
Superseded by the AAAI 2008 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
Heuristic search using algorithms such as A* and IDA* is the
prevalent method for obtaining optimal sequential solutions for
classical planning tasks. Theoretical analyses of these
classical search algorithms, such as the well-known results of
Pohl, Gaschnig and Pearl, suggest that such heuristic search
algorithms can obtain better than exponential scaling behaviour,
provided that the heuristics are accurate enough.
Here, we show that for a number of common planning benchmark
domains, including ones that admit optimal solution in
polynomial time, general search algorithms such as A* must
necessarily explore an exponential number of search
nodes even under the optimistic assumption of almost
perfect heuristic estimators, whose heuristic error is
bounded by a small additive constant.
Our results shed some light on the comparatively bad performance
of optimal heuristic search approaches in "simple" domains such
as GRIPPER. They suggest that in many domains, further
improvements in run-time require changes to other parts of the
planning algorithm than the heuristic estimator.
-
Malte Helmert and Robert Mattmüller.
On the Accuracy of Admissible Heuristic Functions in
Selected Planning Domains.
In
Proceedings of the
ICAPS-2007
Workshop on Heuristics for Domain-independent Planning: Progress,
Ideas, Limitations, Challenges.
2007.
Superseded by the AAAI 2008 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
The efficiency of optimal planning algorithms based on heuristic
search crucially depends on the accuracy of the heuristic
function used to guide the search. Often, we are interested in
domain-independent heuristics for planning. In assessing the
limitations of domain-independent heuristic planning, it appears
interesting to analyse the (in)accuracy of common
domain-independent planning heuristics in the IPC benchmark
domains. For a selection of these domains, we analytically
investigate the accuracy of the h+
heuristic, the hk family of heuristics, and
certain (additive) pattern database heuristics, compared to the
optimal heuristic h*. Whereas
h+ and additive pattern database heuristics
usually return cost estimates proportional to the true cost,
non-additive hk and non-additive
pattern-database heuristics can yield results underestimating
the true cost by arbitrarily large factors.
-
Silvia Richter, Malte Helmert and Charles Gretton.
A Stochastic Local Search Approach to Vertex Cover.
In
Proceedings of the 30th Annual German Conference on Artificial
Intelligence (KI 2007), pp. 412-426.
2007.
(Show abstract)
(Hide abstract)
(PDF)
We introduce a novel stochastic local search algorithm for the
vertex cover problem. Compared to current exhaustive search
techniques, our algorithm achieves excellent performance on a
suite of problems drawn from the field of biology. We also
evaluate our performance on the commonly used DIMACS benchmarks
for the related clique problem, finding that our approach is
competitive with the current best stochastic local search
algorithm for finding cliques. On three very large problem
instances, our algorithm establishes new records in solution
quality.
-
Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet and Sven Koenig.
Domain-Independent Construction of Pattern Database
Heuristics for Cost-Optimal Planning.
In
Proceedings of the 22nd AAAI Conference on Artificial
Intelligence (AAAI 2007), pp. 1007-1012.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
Heuristic search is a leading approach to domain-independent
planning. For cost-optimal planning, however, existing
admissible heuristics are generally too weak to effectively
guide the search. Pattern database heuristics (PDBs), which are
based on abstractions of the search space, are currently one of
the most promising approaches to developing better admissible
heuristics. The informedness of PDB heuristics depends crucially
on the selection of appropriate abstractions (patterns).
Although PDBs have been applied to many search problems,
including planning, there are not many insights into how to
select good patterns, even manually. What constitutes a good
pattern depends on the problem domain, making the task even more
difficult for domain-independent planning, where the process
needs to be completely automatic and general. We present a novel
way of constructing good patterns automatically from the
specification of planning problem instances. We demonstrate that
this allows a domain-independent planner to solve planning
problems optimally in some very challenging domains, including a
STRIPS formulation of the Sokoban puzzle.
-
Malte Helmert, Robert Mattmüller and Sven Schewe.
Selective Approaches for Solving Weak Games.
In
Proceedings of the Fourth International Symposium on
Automated Technology for Verification and Analysis (ATVA 2006), pp. 200-214.
Springer-Verlag 2006.
(Show abstract)
(Hide abstract)
(PDF)
Model-checking alternating-time properties has recently
attracted much interest in the verification of distributed
protocols. While checking the validity of a specification in
alternating-time temporal logic (ATL) against an explicit
model is cheap (linear in the size of the formula and the
model), the problem becomes EXPTIME-hard when symbolic
models are considered. Practical ATL model-checking therefore
often consumes too much computation time to be tractable.
In this paper, we describe a novel approach for ATL
model-checking, which constructs an explicit weak model-checking
game on-the-fly. This game is then evaluated using heuristic
techniques inspired by efficient evaluation algorithms for
and/or-trees.
To show the feasibility of our approach, we compare its
performance to the ATL model-checking system MOCHA on some
practical examples. Using very limited heuristic guidance, we
achieve a significant speedup on these benchmarks.
-
Malte Helmert, Robert Mattmüller and Gabriele Röger.
Approximation Properties of Planning Benchmarks.
In
Proceedings of the 17th European Conference on Artificial
Intelligence (ECAI 2006), pp. 585-589.
2006.
(Show abstract)
(Hide abstract)
(PDF)
For many classical planning domains, the computational complexity of
non-optimal and optimal planning is known. However, little is known
about the area in between the two extremes of finding some plan
and finding optimal plans. In this contribution, we provide a
complete classification of the propositional domains from the first four
International Planning Competitions with respect to the approximation
classes PO, PTAS, APX, poly-APX, and NPO.
-
Malte Helmert.
New Complexity Results for Classical Planning Benchmarks.
In
Proceedings of the Sixteenth International Conference on Automated
Planning and Scheduling
(ICAPS 2006), pp. 52-61.
AAAI Press 2006.
(Show abstract)
(Hide abstract)
(PDF)
The 3rd and 4th International Planning Competitions have
enriched the set of benchmarks for classical propositional
planning by a number of novel and interesting planning domains.
Although they are commonly used for the purpose of evaluating
planner performance, the planning domains themselves have not
yet been studied in depth. In this contribution, we prove
complexity results for the decision problems related to finding
some plan, finding an optimal sequential
plan, and finding an optimal parallel plan in
these planning domains. Our results also provide some insights
into the question why planning is hard for some of the
domains under consideration.
-
Sebastian Kupferschmid and Malte Helmert.
A Skat Player Based on Monte Carlo Simulation.
In
H. Jaap van den Herik, Paolo Ciancarini and H. H. L. M. Donkers (eds.),
Proceedings of the Fifth International Conference on
Computer and Games (CG 2006), pp. 135-147.
Springer-Verlag 2006.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We apply Monte Carlo simulation and alpha-beta search to the
card game of Skat, which is similar to Bridge, but
different enough to require some new algorithmic ideas besides
the techniques developed for Bridge. Our Skat-playing program
integrates well-known techniques such as move ordering
with two new search enhancements. Quasi-symmetry
reduction generalizes symmetry reductions, popularized by
Ginsberg's Partition Search algorithm, to search states which
are "almost equivalent". Adversarial heuristics
generalize ideas from single-agent search algorithms like A* to
two-player games, leading to guaranteed lower and upper bounds
for the score of a game position. Combining these techniques
with state-of-the-art tree search algorithms, our program
determines the game-theoretical value of a typical Skat hand
(with perfect information) in 10 milliseconds.
-
Malte Helmert.
The Fast Downward Planning System.
Journal of Artificial Intelligence Research 26, pp. 191-246. 2006.
(Show abstract)
(Hide abstract)
(PDF)
Fast Downward is a classical planning system based on heuristic
search. It can deal with general deterministic planning problems
encoded in the propositional fragment of PDDL2.2, including
advanced features like ADL conditions and effects and derived
predicates (axioms). Like other well-known planners such as HSP
and FF, Fast Downward is a progression planner, searching the
space of world states of a planning task in the forward
direction. However, unlike other PDDL planning systems, Fast
Downward does not use the propositional PDDL representation of a
planning task directly. Instead, the input is first translated
into an alternative representation called multi-valued
planning tasks, which makes many of the implicit constraints
of a propositional planning task explicit. Exploiting this
alternative representation, Fast Downward uses hierarchical
decompositions of planning tasks for computing its heuristic
function, called the causal graph heuristic, which is
very different from traditional HSP-like heuristics based on
ignoring negative interactionse of operators.
In this article, we give a full account of Fast Downward's
approach to solving multi-valued planning tasks. We extend our
earlier discussion of the causal graph heuristic to tasks
involving axioms and conditional effects and present some novel
techniques for search control that are used within Fast
Downward's best-first search algorithm: preferred
operators transfer the idea of helpful actions from local
search to global best-first search, deferred evaluation
of heuristic functions mitigates the negative effect of large
branching factors on search performance, and multi-heuristic
best-first search combines several heuristic evaluation
functions within a single search algorithm in an orthogonal way.
We also describe efficient data structures for fast state
expansion (successor generators and axiom
evaluators) and present a new non-heuristic search algorithm
called focused iterative-broadening search, which
utilizes the information encoded in causal graphs in a novel
way.
Fast Downward has proven remarkably successful: It won the
"classical" (i.e., propositional, non-optimising) track of the
4th International Planning Competition at ICAPS 2004, following
in the footsteps of planners such as FF and LPG. Our experiments
show that it also performs very well on the benchmarks of the
earlier planning competitions and provide some insights about
the usefulness of the new search enhancements.
-
Malte Helmert.
A Planning Heuristic Based on Causal Graph Analysis.
In
Proceedings of the Fourteenth International Conference on
Automated Planning and Scheduling
(ICAPS 2004), pp. 161-170.
AAAI Press 2004.
(Show abstract)
(Hide abstract)
(PDF)
In recent years, heuristic search methods for classical planning
have achieved remarkable results. Their most successful
representative, the FF algorithm, performs well over a wide
spectrum of planning domains and still sets the state of the art
for STRIPS planning. However, there are some planning domains in
which algorithms like FF and HSP perform poorly because their
relaxation method of ignoring the "delete lists" of
STRIPS operators loses too much vital information.
Planning domains which have many dead ends in the search space
are especially problematic in this regard. In some domains, dead
ends are readily found by the human observer yet remain
undetected by all propositional planning systems we are aware
of. We believe that this is partly because the STRIPS
representation obscures the important causal structure
of the domain, which is evident to humans.
In this paper, we propose translating STRIPS problems to a
planning formalism with multi-valued state variables in order to
expose this underlying causal structure. Moreover, we show how
this structure can be exploited by an algorithm for detecting
dead ends in the search space and by a planning heuristic based
on hierarchical problem decomposition.
Our experiments show excellent overall performance on the
benchmarks from the international planning competitions.
-
Malte Helmert.
Complexity results for standard benchmark domains in planning.
Artificial Intelligence 143 (2), pp. 219-262. 2003.
(Show abstract)
(Hide abstract)
(PDF)
The efficiency of AI planning systems is usually evaluated
empirically. For the validity of conclusions drawn from such
empirical data, the problem set used for evaluation is of
critical importance. In planning, this problem set usually, or
at least often, consists of tasks from the various planning
domains used in the first two international planning
competitions, hosted at the 1998 and 2000 AIPS conferences. It
is thus surprising that comparatively little is known about the
properties of these benchmark domains, with the exception of
BLOCKSWORLD, which has been studied extensively by
several research groups.
In this contribution, we try to remedy this fact by providing a
map of the computational complexity of non-optimal and optimal
planning for the set of domains used in the competitions. We
identify a common transportation theme shared by the
majority of the benchmarks and use this observation to define
and analyze a general transportation problem that generalizes
planning in several classical domains such as
LOGISTICS, MYSTERY and GRIPPER. We
then apply the results of that analysis to the actual
transportation domains from the competitions. We next examine
the remaining benchmarks, which do not exhibit a strong
transportation feature, namely SCHEDULE and
FREECELL.
Relating the results of our analysis to
empirical work on the behavior of the recently very successful
FF planning system, we observe that our theoretical
results coincide well with data obtained from empirical
investigations.
-
Malte Helmert.
Decidability and Undecidability Results for Planning with
Numerical State Variables.
In
M. Ghallab, J. Hertzberg and P. Traverso (eds.),
Proceedings of the Sixth International Conference on
Artificial Intelligence Planning and Scheduling
(AIPS 2002), pp. 303-312.
AAAI Press 2002.
(Show abstract)
(Hide abstract)
(PDF)
These days, propositional planning can be considered a quite
well-understood problem. Good algorithms are known that will
solve a wealth of very different and sometimes challenging
planning tasks, and theoretical computational properties of both
general STRIPS-style planning and the best-known benchmark
problems have been established.
However, propositional planning has a major drawback: The
formalism is too weak to allow for the easy encoding of many
genuinely interesting planning problems, specifically those
involving numbers. A recent effort to enhance the PDDL planning
language to cope with (among other additions) numerical state
variables, to be used at the third international planning
competition, has increased interest in these issues.
In this contribution, we analyze "STRIPS with numbers" from a
theoretical point of view. Specifically, we show that the
introduction of numerical state variables makes the planning
problem undecidable in the general case and many restrictions
thereof and identify special cases for which we can provide
decidability results.
-
Stefan Edelkamp and Malte Helmert.
The Model Checking Integrated Planning System (MIPS).
AI Magazine 22 (3), pp. 67-71. 2001.
(Show abstract)
(Hide abstract)
(PDF)
MIPS was the first general planning system based on model
checking methods. It can handle the STRIPS subset of the PDDL
language and some additional features from ADL, namely negative
preconditions and (universal) conditional effects. At the AIPS
2000 conference, MIPS was one of five planning systems to
be awarded for "Distinguished Performance" in the fully
automated track.
This short paper gives a brief introduction to BDDs and explains
the basic planning algorithm employed by MIPS, using a
simple logistics problem as an example.
-
Malte Helmert.
On the Complexity of Planning in Transportation Domains.
In
A. Cesta and D. Borrajo (eds.),
Proceedings of the 6th European Conference on Planning
(ECP 2001), pp. 349-360.
2001.
(Show abstract)
(Hide abstract)
(PDF)
The efficiency of AI planning systems is usually evaluated
empirically. Some benchmark problems are of particular
importance in this context, especially the ones used in the
competitions of the 1998 and 2000 AIPS conferences. Many of
these benchmarks share a common theme of transporting
portables, making use of mobiles traversing a
map of locations and roads.
In this contribution, we embed these benchmarks into a
well-structured hierarchy of transportation problems
and study the computational complexity of optimal and
non-optimal planning in this family of domains. We identify the
key domain features that make transportation tasks hard and try
to shed some light on the recent success of planning systems
based on heuristic local search, as observed in the AIPS 2000
competition.
-
Christian Dornhege, Alexander Kleiner, Andreas Hertle and Andreas Kolling.
Multirobot Coverage Search in Three Dimensions.
Journal of Field Robotics 33 (4), pp. 537-558. 2016.
(Show abstract)
(Hide abstract)
(PDF)
Searching for objects and observing parts of a known environment efficiently is a fundamental problem in
many real-world robotic applications, e.g., household robots searching for objects, inspection robots searching
for leaking pipelines, and rescue robots searching for survivors after a disaster. We consider the problem of
identifying and planning sequences of sensor locations from which robot sensors can observe and cover complex
three-dimensional (3D) environments while traveling only short distances. Our approach is based on sampling
and ranking a large number of sensor locations for a 3D environment represented by an OctoMap. The visible
area from these sensor locations induces a minimal partition of the 3D environment that we exploit for planning
sequences of sensor locations with short travel times efficiently. We present multiple planning algorithms
designed for single robots and for multirobot teams. These algorithms include variants that are greedy, optimal,
or based on decomposing the planning problem into a set cover and traveling salesman problem. We evaluated
and compared these algorithms empirically in simulation and real-world robot experiments with up to four
robots. Our results demonstrate that, despite the intractability of the overall problem, computing and executing
effective solutions for multirobot coverage search in real 3D environments is feasible and ready for real-world
applications.
-
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 Dornhege, Alexander Kleiner and Andreas Kolling.
Coverage Search in 3D.
In
Proceedings of the Symposium on Safety Security and Rescue Robotics (SSRR).
2013.
(PDF)
(BIB)
-
Christian Dornhege and Alexander Kleiner.
A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
Advanced Robotics 27 (6). 2013.
(BIB)
-
Christian Dornhege and Alexander Kleiner.
A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
In
Proceedings of the IEEE International Symposium on Safety, Security and Rescue Robotics (SSRR).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the problem of an autonomous robot searching for objects in unknown 3d space. Similar to the well known frontier-based exploration in 2d, the problem is to determine a minimal sequence of sensor viewpoints until the entire search space has been explored. We introduce a novel approach that combines the two concepts of voids, which are unexplored volumes in 3d, and frontiers, which are regions on the boundary between voids and explored space. Our approach has been evaluated on a mobile platform equipped with a manipulator searching for victims in a simulated USAR setup. First results indicate the real-world capability and search efficiency of the proposed method.
-
Alexander Kleiner, Dali Sun and D. Meyer-Delius.
ARMO: Adaptive Road Map Optimization for Large Robot Teams.
In
Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Autonomous robot teams that simultaneously dispatch transportation tasks are playing more and more an important role in present logistic centers and manufacturing plants. In this paper we consider the problem of robot motion planning for large robot teams in the industrial domain. We present adaptive road map optimization (ARMO) that is capable of adapting the road map in real time whenever the environment has changed. Based on linear programming, ARMO computes an optimal road map according to current environmental constraints (including human whereabouts) and the current demand for transportation tasks from loading stations in the plant. For detecting dynamic changes, the environment is describe by a grid map augmented with a hidden Markov model (HMM). We show experimentally that ARMO outperforms decoupled planning in terms of computation time and time needed for task completion.
-
Alexander Kleiner, A. Kolling, K. Sycara and M. Lewis.
Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain.
Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS). 2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Searching for moving targets in large environments is a challenging task that is relevant in several problem domains, such as capturing an invader in a camp, guarding security facilities, and searching for victims in large-scale search and rescue scenarios. The guaranteed search problem is to coordinate the search of a team of agents to guarantee the discovery of all targets. In this paper we present a self-contained solution to this problem in 2.5D real-world domains represented by digital elevation models (DEMs). We introduce hierarchical sampling on DEMs for selecting heuristically the close to minimal set of locations from which the entire surface of the DEM can be guarded. Locations are utilized to form a search graph on which search strategies for mobile agents are computed. For these strategies schedules are derived which include agent paths that are directly executable in the terrain. Presented experimental results demonstrate the performance of the method. The practical feasibility of our approach has been validated during a field experiment at the Gascola robot training site where teams of humans equipped with iPads successfully searched for adversarial and omniscient evaders. The field demonstration is the largest-scale implementation of a guaranteed search algorithm to date.
-
Q. Hamp, L. Reindl and Alexander Kleiner.
Lessons Learned from German Research for USAR.
In
Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We present lessons learned in USAR research within the framework of the German research project I-LOV.
After three years of development first field tests have been carried out by professionals such as the
Rapid Deployment Unit for Salvage Operations Abroad (SEEBA). We present results from evaluating search
teams in simulated USAR scenarios equipped with newly developed technical search means and digital data input terminals developed in the I- LOV project.
In particular, the bioradar, a ground-penetrating radar system for the detection of humanoid movements, a semi-active video probe for rubble pile exploration of more than 10 m length, and the decision support system FRIEDAA were evaluated and compared with conventional search methods. Results of this evaluation indicate that the developed technologies foster advantages in USAR, which are discussed in this paper.
-
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.
-
D. Meyer-Delius, M. Beinhofer, Alexander Kleiner and W. Burgard.
Reducing the Ambiguity in the Environment by Placing Artificial Landmarks to Improve Mobile Robot Localization.
In
Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Robust and reliable localization is a fundamental prerequisite for successful robot navigation. Although there exist many solutions to the localization problem, environments can be inherently ambiguous so that different robot locations cannot to be distinguished using the sensors of the robot. This is particularly critical in comercial environments, for example in warehouses, containing long corridors and symmetric structures. This ambiguity makes localization approaches more likely to diverge or even prevent the pose of the robot from being uniquely estimated at all. In this paper we propose the utilization of artificial landmarks to reduce the inherent ambiguity in the environment, and present an efficient, localization-oriented approach to landmark placement. Our approach provides us with both the location and number of landmarks to be placed in order to improve the localization performance of the robot in a given environment. Experimental results show that by intelligently placing the landmarks we can improve the localization performance of the robot.
-
A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara.
Computing and Executing Strategies for Moving Target Search.
In
Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA).
2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We address the problem of searching for moving targets in large outdoor environments represented by height maps. To solve the problem we present a complete system that computes from an annotated height map a graph representation and search strategies based on worst-case assumptions about all targets. These strategies are then used to compute a schedule and task assignment for all agents. We improve the graph construction from previous work and for the first time present a method that computes a schedule to minimize the execution time. For this we consider travel times of agents determined by a path planner on the height map. We demonstrate the entire system in a real environment with an area of 700,000m2 in which eight human agents search for two intruders using mobile computing devices (iPads). To the best of our knowledge this is the first demonstration of a search system applied to such a large environment.
-
R. Kümmerle, B. Steder, Christian Dornhege, Alexander Kleiner, G. Grisetti and W. Burgard.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
Autonomous Robots 30, pp. 25-39. 2011.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, most existing solutions to the SLAM problem learn the maps from scratch and have no means for incorporating prior information. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. It inserts correspondences found between stereo and three-dimensional range data and the aerial images as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired even in mixed in- and outdoor environments by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency.
-
Wei Mou and Alexander Kleiner.
Online Learning Terrain Classification for Adaptive Velocity Control.
In
Proceedings of the IEEE Int. Workshop on Safety, Security and Rescue Robotics
(SSRR 2010).
2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Safe teleoperation during critical missions, such as urban search and rescue and bomb disposal, requires careful velocity control when different types of terrain are found in the scenario. This can particularly be challenging when mission time is limited and the operator’s field of view affected.
This paper presents a method for online adapting robot velocities according to the terrain classification from vision and laser readings. The classifier adapts itself to illumination variations, and can be improved online given feedback from the operator.
-
Andreas Kolling, Alexander Kleiner, Michael Lewis and Katia Sycara.
Solving Pursuit-Evasion Problems on Height Maps.
In
IEEE International Conference on Robotics and Automation (ICRA 2010)
Workshop: Search and Pursuit/Evasion in the Physical World: Efficiency, Scalability, and Guarantees
(WSPE ICRA 2010).
2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment
represented by a height map. Such a representation is particularly suitable for large-scale outdoor
pursuit-evasion. By allowing height information we not only capture some aspects of 3d visibility but
can also consider target heights. In our approach we construct a graph representation of the environment
by sampling points and their detection sets which extend the usual notion of visibility. Once a graph
is constructed we compute strategies on this graph using a modification of previous work on graph-searching.
This strategy is converted into robot paths that are planned on the height map by classifying the terrain
appropriately. In experiments we investigate the performance of our approach and provide examples
including a map of a small village with surrounding hills and a sample map with multiple loops and
elevation plateaus. Experiments are carried out with varying sensing ranges as well as target and sensor
heights. To the best of our knowledge the presented approach is the first viable solution to 2.5d
pursuit-evasion with height maps.
-
Daniel Maier and Alexander Kleiner.
Improved GPS Sensor Model for Mobile Robots in Urban Terrain.
In
IEEE International Conference on Robotics and Automation
(ICRA 2010), pp. 4385-4390.
2010.
(Video).
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Autonomous robot navigation in outdoor scenarios gains increasing importance
in various growing application areas. Whereas in non-urban domains such as deserts
the problem of successful GPS-based navigation appears to be almost solved,
navigation in urban domains particularly in the close vicinity of buildings is
still a challenging problem. In such situations GPS accuracy significantly drops
down due to multiple signal reflections with larger objects causing the so-called multipath error.
In this paper we contribute a novel approach for incorporating multi- path errors into the conventional
GPS sensor model by analyzing environmental structures from online generated point clouds. The approach
has been validated by experimental results conducted with an all- terrain robot operating in scenarios
requiring close- to-building navigation.
Presented results show that positioning accuracy can significantly be improved within urban domains.
-
Alexander Kleiner and Christian Dornhege.
Mapping for the Support of First Responders in Critical Domains.
Journal of Intelligent and Robotic Systems (JINT), pp. 1-29. 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In critical domains such as urban search and rescue (USAR), and bomb disposal, the deployment of teleoperated robots is essential to reduce the risk of first responder personnel. Teleoperation is a difficult task, particularly when controlling robots from an isolated safety zone. In general, the operator has to solve simultaneously the problems of mission planning, target identification, robot navigation, and robot control. We introduce a system to support teleoperated navigation with real-time mapping consisting of a two-step scan matching method that re-considers data associations during the search. The algorithm processes data from laser range finder and gyroscope only, thereby it is independent from the robot platform. Furthermore, we introduce a user-guided procedure for improving the global consistency of maps generated by the scan matcher. Globally consistent maps are computed by a graph-based maximum likelihood method that is biased by localizing crucial parts of the scan matcher trajectory on a prior given geo-tiff image. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system was evaluated in a test maze by first responders during the Disaster City event in Texas 2008.
-
Sören Schwertfeger, Adam Jacoff, Chris Scrapper, Johannes Pellenz and Alexander Kleiner.
Evaluation of Maps using Fixed Shapes: The Fiducial Map Metric.
In
Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), pp. 344-351.
NIST 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Mapping is an important task for mobile robots. Assessing the quality of those maps is an open topic. A new approach on map evaluation is presented here. It makes use of artificial objects placed in the environment named "Fiducials". Using the known ground-truth positions and the positions of the fiducials identified in the map, a number of quality attributes can be assigned to that map. Depending on the application domain those attributes are weighed to compute a final score. During the 2010 NIST Response Robot Evaluation Exercise at Disaster City an area was populated with fiducials and different mapping runs were performed. The maps generated there are assessed in this paper demonstrating the Fiducial approach. Finally this map scoring algorithm is compared to other approaches found in literature.
-
A. Kolling, Alexander Kleiner, M. Lewis and and K. Sycara.
Pursuit-Evasion in 2.5d based on Team-Visibility.
In
Proceedings of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems
(IROS 2010), pp. 4610-4616.
2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion, captures some aspects of 3d visibility and can include target heights. In our approach we construct a graph representation of the environment by sampling points and computing detection sets, an extended notion of visibility. Moreover, the constructed graph captures overlaps of detection sets allowing for a coordinated team-based clearing of the environment with robots that move to the sampled points. Once a graph is constructed we compute strategies on it utilizing previous work on graph-searching. This is converted into robot paths that are planned on the height map by classifying the terrain appropriately. In experiments we investigate the performance of our approach and provide examples including a sample map with multiple loops and elevation plateaus and two realistic maps, one of a village and one of a mountain range. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps.
-
Dali Sun, Alexander Kleiner and and C. Schindelhauer.
Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks.
In
Proceedings of the 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems
(AAMAS 2010), pp. 923-930.
2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Although a remarkably high degree of automation has been reached in production and intra-logistics nowadays, human labor is still used for transportation using handcarts and forklifts. High labor cost and risk of injury are the undesirable consequences. Alternative approaches in automated warehouses are fixed installed conveyors installed either overhead or floor-based. The drawback of such solutions is the lack of flexibility, which is necessary when the production lines of the company change. Then, such an installation has to be re-built. In this paper, we propose a novel approach of decentralized teams of autonomous robots performing intra-logistics tasks using distributed algorithms. Centralized solutions suffer from limited scalability and have a single point of failure. The task is to transport material between stations keeping the communication network structure intact and most importantly, to facilitate a fair distribution of robots among loading stations. Our approach is motivated by strategies from peer-to-peer-networks and mobile ad-hoc networks. In particular we use an adapted version of distributed heterogeneous hash tables (DHHT) for distributing the tasks and localized communication. Experimental results presented in this paper show that our method reaches a fair distribution of robots over loading stations.
-
Alexander Kleiner, Chris Scrapper and Adam Jacoff.
RoboCupRescue Interleague Challenge 2009: Bridging the gap between Simulation and Reality.
In
Proceedings of the Int. Workshop on Performance Metrics for Intelligent Systems
(Permis 2009), pp. 123-129.
NIST 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Teleoperation is a difficult task, particularly when
controlling robots from an isolated operator station.
In general, the operator has to solve nearly blindly the problems of mission
planning, target identification, robot navigation, and robot control at the same time.
The goal of the proposed system is to support teleoperated navigation
with real-time mapping.
We present a novel scan matching technique that re-considers data
associations during the search, enabling robust pose estimation even under
varying roll and pitch angle of the robot enabling mapping
on rough terrain.
The approach has been implemented as an embedded system and extensively tested
on robot platforms designed for teleoperation in critical situations, such as bomb
disposal.
Furthermore,
the system has been evaluated in a test maze by first responders during
the Disaster City event in Texas 2008.
Finally, experiments conducted within different environments show that
the system yields comparably accurate maps in real-time when
compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.
-
Alexander Kleiner and Christian Dornhege.
Operator-Assistive Mapping in Harsh Environments.
In
IEEE International Workshop on Safety, Security and Rescue Robotics
(SSRR 2009), pp. 1-6.
2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Teleoperation is a difficult task, particularly when
controlling robots from an isolated operator station.
In general, the operator has to solve nearly blindly the problems of mission
planning, target identification, robot navigation, and robot control at the same time.
The goal of the proposed system is to support teleoperated navigation
with real-time mapping.
We present a novel scan matching technique that re-considers data
associations during the search, enabling robust pose estimation even under
varying roll and pitch angle of the robot enabling mapping
on rough terrain.
The approach has been implemented as an embedded system and extensively tested
on robot platforms designed for teleoperation in critical situations, such as bomb
disposal.
Furthermore,
the system has been evaluated in a test maze by first responders during
the Disaster City event in Texas 2008.
Finally, experiments conducted within different environments show that
the system yields comparably accurate maps in real-time when
compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.
-
Rainer Kümmerle, Bastian Steder, Christian Dornhege, Michael Ruhnke, Giorgio Grisetti, Cyrill Stachniss and Alexander Kleiner.
On Measuring the Accuracy of SLAM Algorithms.
Autonomous Robots 27 (4), pp. 387-407. 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In this paper, we address the problem of creating an objective benchmark for evaluating SLAM approaches. We propose a framework for analyzing the results of a SLAM approach based on a metric for measuring the error of the corrected trajectory. This metric uses only relative relations between poses and does not rely on a global reference frame. This overcomes serious shortcomings of approaches using a global reference frame to compute the error. Our method furthermore allows us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot.
We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the robotics community. The relations have been obtained by manually matching laser-range observations to avoid the errors caused by matching algorithms. Our benchmark framework allows the user to easily analyze and objectively compare different SLAM approaches.
-
Wolfram Burgard, Cyrill Stachniss, Giorgio Grisetti, Bastian Steder, Rainer Kümmerle, Christian Dornhege, Michael Ruhnke, Alexander Kleiner and Juan D. Tardos.
A Comparison of SLAM Algorithms Based on a Graph of Relations.
In
Proceedings of the 2009 IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS 2009), pp. 2089-2095.
IEEE 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In this paper, we address the problem of creating
an objective benchmark for comparing SLAM approaches.
We propose a framework for analyzing the results of SLAM
approaches based on a metric for measuring the error of the
corrected trajectory. The metric uses only relative relations
between poses and does not rely on a global reference frame.
The idea is related to graph-based SLAM approaches in
the sense that it considers the energy needed to deform the
trajectory estimated by a SLAM approach to the ground
truth trajectory. Our method enables us to compare SLAM
approaches that use different estimation techniques or different
sensor modalities since all computations are made based on the
corrected trajectory of the robot. We provide sets of relative
relations needed to compute our metric for an extensive set
of datasets frequently used in the SLAM community. The
relations have been obtained by manually matching laser-range
observations. We believe that our benchmarking framework
allows the user an easy analysis and objective comparisons
between different SLAM approaches.
-
Rainer Kümmerle, Bastian Steder, Christian Dornhege, Alexander Kleiner, Giorgio Grisetti and Wolfram Burgard.
Large Scale Graph-based SLAM using Aerial Images as Prior Information.
In
Proceedings of 2009 Robotics: Science and Systems (RSS 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To effectively navigate in their environments and accurately
reach their target locations, mobile robots require a globally
consistent map of the environment. The problem of learning a map
with a mobile robot has been intensively studied in the past and
is usually referred to as the simultaneous localization and
mapping (SLAM) problem. However, existing solutions to the SLAM
problem typically rely on loop-closures to obtain global
consistency and do not exploit prior information even if it is
available. In this paper, we present a novel SLAM approach that
achieves global consistency by utilizing publicly accessible
aerial photographs as prior information. Our approach inserts
correspondences found between three-dimensional laser range
scans and the aerial image as constraints into a graph-based
formulation of the SLAM problem. We evaluate our algorithm based
on large real-world datasets acquired in a mixed in- and outdoor
environment by comparing the global accuracy with
state-of-the-art SLAM approaches and GPS. The experimental
results demonstrate that the maps acquired with our method show
increased global consistency.
-
Dali Sun, Alexander Kleiner and T. M. Wendt.
Multi-Robot Range-Only SLAM by Active Sensor Nodes for Urban Search and Rescue.
In
Robocup 2008: Robot Soccer World Cup XII, pp. 318-330.
Springer 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To jointly map an unknown environment with a team of autonomous robots is a challenging problem, particularly in large environments, as for example the devastated area after a disaster. Under such conditions standard methods for Simultaneous Localization And Mapping (SLAM) are difficult to apply due to possible misinterpretations of sensor data, leading to erroneous data association for loop closure. We consider the problem of multi-robot range-only SLAM for robot teams by solving the data association problem with wireless sensor nodes that we designed for this purpose. The memory of these nodes is utilized for the exchange of map data between multiple robots, facilitating loop-closures on jointly generated maps. We introduce RSLAM, which is a variant of FastSlam, extended for range-only measurements and the multi-robot case. Maps are generated from robot odometry and range estimates, which are computed from the RSSI (Received Signal Strength Indication). The proposed method has been extensively tested in USARSim, which serves as basis for the Virtual Robots competition at RoboCup, and by real-world experiments with a team of mobile robots. The presented results indicates that the approach is capable of building consistent maps in presence of real sensor noise, as well as to improve mapping results of multiple robots by data sharing.
-
Alexander Kleiner, G. Steinbauer and F. Wotawa.
Towards automated online diagnosis of robot navigation software.
In
Proc. of Int. Conf. on Simulation, Modeling and Programming for Autonomous Robots (SIMPAR), pp. 159-170.
Springer 2008.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Control software of autonomous mobile robots comprises a number of software modules that typically interact in a very complex way. Their proper interaction and the robustness of each single module strongly influences the safety during navigation in the field. Particularly in unstructured environments, unforeseen situations are likely to occur, causing erroneous behaviors of the robot. The proper handling of such situations requires an understanding of cause and effect within the complex interactions of the system. In this paper we present an approach which is able to automatically derive a model of the communication behavior within a component-orientated control software. The model can be used for online diagnosis in order to increase system robustness during runtime. We demonstrate model learning and system diagnosis on three different robot systems which were controlled by software modules communicating based on the widely used IPC (Inter Process Communication) standard. The demonstrated learning and diagnosis was carried out without any a priori knowledge about the systems.
-
Christian Dornhege and Alexander Kleiner.
Fully autonomous planning and obstacle negotiation on rough terrain using behavior maps.
In
Video Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2007).
San Diego, California 2007.
-
Christian Dornhege and Alexander Kleiner.
Behavior maps for online planning of obstacle negotiation and climbing on rough terrain.
In
Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2007), pp. 3005-3011.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as Obstacle Negotiation (ON). In this paper, we introduce a planning framework that extends ON to the general case, where different types of terrain classes directly map to specific robot skills, such as climbing stairs and ramps. This extension is based on a new concept called behavior maps, which is utilized for the planning and execution of complex skills. Behavior maps are directly generated from elevation maps, i.e. two-dimensional grids storing in each cell the corresponding height of the terrain surface, and a set of skill descriptions. Results from extensive experiments are presented, showing that the method enables the robot to explore successfully rough terrain in real-time, while selecting the optimal trajectory in terms of costs for navigation and skill execution.
-
Alexander Kleiner and R. Kümmerle.
Genetic MRF model optimization for real-time victim detection in Search and Rescue.
In
Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2007), pp. 3025-3030.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
One primary goal in rescue robotics is to deploy a team of robots for coordinated victim search after a disaster. This requires robots to perform subtasks, such as victim detection, in real-time. Human detection by computationally cheap techniques, such as color thresholding, turn out to produce a large number of false-positives. Markov Random Fields (MRFs) can be utilized to combine the local evidence of multiple weak classifiers in order to improve the detection rate. However, inference in MRFs is computational expensive. In this paper we present a novel approach for the genetic optimizing of the building process of MRF models. The genetic algorithm determines offline relevant neighborhood relations with respect to the data, which are then utilized for generating efficient MRF models from video streams during runtime. Experimental results clearly show that compared to a Support Vector Machine (SVM) based classifier, the optimized MRF models significantly reduce the false-positive rate. Furthermore, the optimized models turned out to be up to five times faster then the non-optimized ones at nearly the same detection rate.
-
Alexander Kleiner and Christian Dornhege.
Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
Journal of Field Robotics 24, pp. 723-745. 2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Urban Search And Rescue (USAR) is a time critical task. Rescue teams have to explore a large terrain within a short amount of time in order to locate survivors after a disaster. One goal in Rescue Robotics is to have a team of heterogeneous robots that explore autonomously, or partially guided by an incident commander, the disaster area. Their task is to jointly create a map of the terrain and to register victim locations, which can further be utilized by human task forces for rescue. Basically, the robots have to solve autonomously in real-time the problem of Simultaneous Localization and Mapping (SLAM), consisting of a continuous state estimation problem and a discrete data association problem. Extraordinary circumstances after a real disaster make it very hard to apply common techniques. Many of these have been developed under strong assumptions, for example, they require polygonal structures, such as typically found in office-like environments. Furthermore, most techniques are not deployable in real-time. In this paper we propose real-time solutions for localization and mapping, which all have been extensively evaluated within the test arenas of the National Institute of Standards and Technology (NIST). We specifically deal with the problems of vision-based pose tracking on tracked vehicles, the building of globally consistent maps based on a network of RFID tags, and the building of elevation maps from readings of a tilted Laser Range Finder (LRF). Our results show that these methods lead under modest computational requirements to good results within the utilized testing arenas.
-
S. Balakirsky, S. Carpin, Alexander Kleiner, M. Lewis, A. Visser, J. Wang and V.A. Ziparo.
Towards heterogeneous robot teams for disaster mitigation: Results and Performance Metrics from Robocup Rescue.
Journal of Field Robotics 24, pp. 943-967. 2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Urban Search And Rescue is a growing area of robotic research. The RoboCup Federation has recognized this, and has created the new Virtual Robots competition to complement its existing physical robot and agent competitions. In order to successfully compete in this competition, teams need to field multi-robot solutions that cooperatively explore and map an environment while searching for victims. This paper presents the results of the first annual RoboCup Rescue Virtual competition. It provides details on the metrics used to judge the contestants as well as summaries of the algorithms used by the top four teams. This allows readers to compare and contrast these effective approaches. Furthermore, the simulation engine itself is examined and real-world validation results on the engine and algorithms are offered.
-
V.A. Ziparo, Alexander Kleiner, L. Marchetti, A. Farinelli and and D. Nardi.
Cooperative Exploration for USAR Robots with Indirect Communication.
In
Proceedings of the 6th IFAC Symposium on Intelligent Autonomous
Vehicles (IAV 2007).
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
To coordinate a team of robots for exploration is a challenging problem, particularly in unstructured areas, as for example post-disaster scenarios where direct communication is severely constrained. Furthermore, conventional methods of SLAM, e.g. those performing data association based on visual features, are doomed to fail due to bad visibility caused by smoke and fire. We use indirect communication (based on RFIDs), to share knowledge and use a gradient-like local search to direct robots towards interesting areas. To share a common frame of reference among robots we use a feature based SLAM approach (where features are RFIDs). The approach has been evaluated on a 3D simulation based on USARSim.
-
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.
-
Alexander Kleiner, Christian Dornhege and Dali Sun.
Mapping disaster areas jointly: RFID -Coordinated SLAM by Humans and Robots.
In
Proceedings of the IEEE International Workshop on Safety, Security
and Rescue Robotics (SSRR 2007), pp. 1-6.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the problem of jointly performing SLAM by humans and robots in Urban Search And Rescue (USAR) scenarios. In this context, SLAM is a challenging task. First, places are hardly re-observable by vision techniques since visibility might be affected by smoke and fire. Second, loop-closure is cumbersome due to the fact that firemen will intentionally try to avoid performing loops when facing the reality of emergency response, e.g.USAR, while they are searching for victims. Furthermore, there might be places that are only accessible to robots, making it necessary to integrate humans and robots into one team for mapping the area after a disaster. In this paper, we introduce a method for jointly correcting individual trajectories of humans and robots by utilizing RFID technology for data association. Hereby the poses of humans and robots are tracked by a PDR (Pedestrian Dead Reckoning), and slippage sensitive odometry, respectively. We conducted extensive experiments with a team of humans, and a human-robot team within a semi-outdoor environment. Results from these experiments show that the introduced method allows to improve single trajectories based on the joint graph, even if they do not contain any loop.
-
H. Kenn and Alexander Kleiner.
Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation.
In
MobileResponse, pp. 106-115.
Springer 2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The coordinated reaction to a large-scale disaster is a challenging research problem. The Robocup rescue simulation league addresses this research problem but is currently lacking an interface to real-world real-time data to test the validity of both simulation and simulated reactions. In this paper, we describe a wearable-computing-based real world interface to the Robocup Resuce simulation software and provide some updated results of preliminary evaluations.
-
Alexander Kleiner and Dali Sun.
Decentralized SLAM for Pedestrians without direct Communication.
In
Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2007), pp. 1461-1466.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We consider the problem of Decentralized Simultaneous Localization And Mapping (DSLAM) for pedestrians in the context of Urban Search And Rescue (USAR). In this context, DSLAM is a challenging task. First, data exchange fails due to cut off communication links. Second, loop-closure is cumbersome due to the fact that fireman will intentionally try to avoid performing loops, when facing the reality of emergency response, e.g. while they are searching for victims. In this paper, we introduce a solution to this problem based on the non-selfish sharing of information between pedestrians for loop-closure. We introduce a novel DSLAM method which is based on data exchange and association via RFID technology, not requiring any radio communication. The approach has been evaluated within both outdoor and semi-indoor environments. The presented results show that sharing information between single pedestrians allows to optimize globally their individual paths, even if they are not able to communicate directly.
-
Alexander Kleiner, Johann Prediger and Bernhard Nebel.
RFID Technology-based Exploration and SLAM for Search And Rescue.
In
Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS 2006), pp. 4054-4059.
Beijing, China 2006.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Robot search and rescue is a time critical task, i.e.
a large terrain has to be explored by multiple robots within
a short amount of time. The efficiency of exploration depends
mainly on the coordination between the robots and hence on the
reliability of communication, which considerably suffers under
the hostile conditions encountered after a disaster. Furthermore,
rescue robots have to generate a map of the environment which
has to be sufficiently accurate for reporting the locations of
victims to human task forces. Basically, the robots have to
solve autonomously in real-time the problem of Simultaneous
Localization and Mapping (SLAM).
This paper proposes a novel method for real-time exploration
and SLAM based on RFID tags that are autonomously distributed
in the environment. We utilized the algorithm of Lu
and Milios [8] for calculating globally consistent maps from
detected RFID tags. Furthermore we show how RFID tags can
be used for coordinating the exploration of multiple robots.
Results from experiments conducted in the simulation and
on a robot show that our approach allows the computationally
efficient construction of a map within harsh environments, and
coordinated exploration of a team of robots.
-
Alexander Kleiner, Christian Dornhege, Rainer Kuemmerle, Michael Ruhnke, Bastian Steder, Bernhard Nebel, Patrick Doherty, Mariusz Wzorek, Piotr Rudol, Gianpaolo Conte, S. Durante and D. Lundstrom.
RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
In
CDROM Proceedings of the International RoboCup Symposium '05.
Bremen, Germany 2006.
(Show abstract)
(Hide abstract)
(PDF)
This paper describes the approach of the RescueRobots Freiburg team,
which 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). Furthermore we introduce linkMAV, a micro aerial
vehicle platform.
Our approach covers RFID-based SLAM and exploration, autonomous detection
of relevant 3D structures, visual odometry, 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.
-
Alexander Kleiner and Vittorio Ziparo.
RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany), Team Description Paper.
In
CDROM Proceedings of the International RoboCup Symposium '06.
Bremen, Germany 2006.
(PDF)
-
Christian Dornhege and Alexander Kleiner.
Visual Odometry for Tracked Vehicles.
In
Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2006).
2006.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Localization and mapping on autonomous robots typically requires a good pose estimate, which is hard to acquire if the vehicle is tracked. In this paper we describe a solution to the pose estimation problem by utilizing a consumer-quality camera and an Inertial Measurement Unit (IMU). The basic idea is to continuously track salient features with the KLT feature tracker over multiple images taken by the camera and to extract from the tracked features image vectors resulting from the robot's motion. Each image vector is taken for a voting that best explains the robot's motion. Image vectors vote according to a previously trained ^\m2102tile coding^\m2112 classificator that assigns to each possible image vector a translation probability. Our results show that the proposed single camera solution leads to sufficiently accurate pose estimates of the tracked vehicle.
-
Alexander Kleiner, N. Behrens and H. Kenn.
Wearable computing meets multiagent systems: A real-world interface for the RoboCupRescue simulation platform.
In
First International Workshop on Agent Technology for Disaster Management at AAMAS06, pp. 116-123.
AAMAS Press 2006.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
One big challenge in disaster response is to get an overview over the degree of damage and to provide this information, together with optimized plans for rescue missions, back to teams in the field. Collapsing infrastructure, limited visibility due to smoke and dust, and overloaded communication lines make it nearly impossible for rescue teams to report the total situation consistently. This problem can only be solved by efficiently integrating data of ^\m2102many^\m2112 observers into a single consistent view. A Global Positioning System (GPS) device in conjunction with a communication device, and sensors or simple input methods for reporting observations, offer a realistic chance to solve the data integration problem. We propose preliminary results from a wearable computing device, acquiring disaster relevant data, such as locations of victims and blockades, and show the data integration into the RoboCupRescue Simulation platform, which is a benchmark for MAS within the RoboCup competitions. We show exemplarily how the data can consistently be integrated and how rescue missions can be optimized by solutions developed on the RoboCupRescue simulation platform. The preliminary results indicate that nowadays wearable computing technology combined with MAS technology can serve as a powerful tool for Urban Search and Rescue (USAR).
-
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.
-
Alexander Kleiner.
Game AI: The shrinking gap between computer games and AI systems Ambient Intelligence.
Ambient Intelligence:The evolution of technology, communication and cognition towards the future of human-computer interaction. 2005.
(PDF)
-
Timo Nuessle, Alexander Kleiner and Michael Brenner.
Approaching Urban Disaster Reality: The ResQ Firesimulator.
In
Proceedings of the International RoboCup Symposium '04.
Lisbon, Portugal 2004.
(PDF)
-
Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger and Joerg Stueckler.
ResQ Freiburg: Team Description and Evaluation, Team Description Paper, Rescue Simulation League.
In
CDROM Proceedings of the International RoboCup Symposium '04.
Lisbon, Portugal 2004.
(PDF)
-
Erik Schulenburg, Thilo Weigel and Alexander Kleiner.
Self-Localization in Dynamic Environments based on Laser and Vision
Data.
In
Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS'03), pp. 998-1004.
Las Vegas, USA 2003.
(PS.GZ)
(PDF)
-
Alexander Kleiner and Thorsten Buchheim.
A Plugin-Based Architecture For Simulation In The F2000 League.
In
Proceedings of the International RoboCup Symposium '03.
Padova, Italy 2003.
(PS.GZ)
(PDF)
-
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.
-
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.
-
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.
-
Julian von Tschammer, Robert Mattmüller and David Speck.
Loopless Top-k Planning.
In
Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022).
2022.
(Show abstract)
(Hide abstract)
(PDF)
In top-k planning, the objective is to determine a set of k cheapest plans that provide several good alternatives to choose from.
Such a solution set often contains plans that visit at least one state more than once. Depending on the application, plans with
such loops are of little importance because they are dominated by a loopless representative and can prevent more meaningful plans
from being found.
In this paper, we motivate and introduce loopless top-k planning. We show how to enhance the state-of-the-art symbolic top-k planner,
symK, to obtain an efficient, sound and complete algorithm for loopless top-k planning. An empirical evaluation shows that our proposed
approach has a higher k-coverage than a generate-and-test approach that uses an ordinary top-k planner, which we show to be incomplete in
the presence of zero-cost loops.
-
David Speck, David Borukhson, Robert Mattmüller and Bernhard Nebel.
On the Compilability and Expressive Power of State-Dependent Action Costs.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358-366.
2021.
(Show abstract)
(Hide abstract)
(PDF)
While state-dependent action costs are practically relevant and have been
studied before, it is still unclear if they are an essential feature of planning
tasks.
In this paper, we study to what extent state-dependent action costs are an
essential feature by analyzing under which circumstances they can be compiled away.
We give a comprehensive classification for combinations of action cost functions and possible
cost measures for the compilations.
Our theoretical results show that if both task sizes and plan lengths are to be
preserved polynomially, then the boundary between compilability and
non-compilability lies between FP and FPSPACE computable action cost
functions (under a mild assumption on the polynomial hierarchy). Preserving task
sizes polynomially and plan lengths linearly at the same time is impossible.
-
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597-605.
2021.
(Show abstract)
(Hide abstract)
(PDF)
A key challenge in satisficing planning is to use multiple heuristics within
one heuristic search. An aggregation of multiple heuristic estimates, for
example by taking the maximum, has the disadvantage that bad estimates of a
single heuristic can negatively affect the whole search. Since the performance
of a heuristic varies from instance to instance, approaches such as algorithm
selection can be successfully applied. In addition, alternating between
multiple heuristics during the search makes it possible to use all heuristics
equally and improve performance. However, all these approaches ignore the
internal search dynamics of a planning system, which can help to select the
most useful heuristics for the current expansion step. We show that dynamic
algorithm configuration can be used for dynamic heuristic selection which takes
into account the internal search dynamics of a planning system. Furthermore, we
prove that this approach generalizes over existing approaches and that it can
exponentially improve the performance of the heuristic search. To learn dynamic
heuristic selection, we propose an approach based on reinforcement learning and
show empirically that domain-wise learned policies, which take the internal
search dynamics of a planning system into account, can exceed existing
approaches.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Michael Thielscher.
Game description language and dynamic epistemic logic compared.
Artificial Intelligence 292. 2021.
(Show abstract)
(Hide abstract)
(Online; DOI)
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). 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 translations between those fragments of GDL-III and DEL.
-
Patrick Caspari, Robert Mattmüller and Tim Schulte.
A Framework to Prove Strong Privacy in Multi-Agent Planning.
In
Proceedings of the 6th Workshop on Distributed and Multi-Agent Planning
(DMAP 2020), pp. 32-39.
2020.
(PDF)
-
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In
Proceedings of the Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL 2020), p. 61–69.
2020.
Superseded by the ICAPS 2021 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF)
A key challenge in satisficing planning is to use multiple heuristics within one
heuristic search. An aggregation of multiple heuristic estimates, for example by
taking the maximum, has the disadvantage that bad estimates of a single heuristic
can negatively affect the whole search. Since the performance
of a heuristic varies from instance to instance, approaches
such as algorithm selection can be successfully applied. In
addition, alternating between multiple heuristics during the
search makes it possible to use all heuristics equally and improve performance.
However, all these approaches ignore the internal search dynamics of a planning
system, which can help to select the most helpful heuristics for the current expansion
step. We show that dynamic algorithm configuration can be used for dynamic heuristic
selection which takes into account the internal search dynamics of a planning system.
Furthermore, we prove that this approach generalizes over existing approaches and that
it can exponentially improve the performance of the heuristic search. To learn dynamic
heuristic selection, we propose an approach based on reinforcement learning and show
empirically that domain-wise learned policies, which take the internal search dynamics
of a planning system into account, can exceed existing approaches in terms of coverage.
-
Dominik Drexler, David Speck and Robert Mattmüller.
Subset-Saturated Transition Cost Partitioning for Optimal Classical Planning.
In
Proceedings of the 12th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2020), p. 23–31.
2020.
Superseded by the ICAPS 2021 paper "Subset-Saturated Transition Cost Partitioning".
(Show abstract)
(Hide abstract)
(PDF)
Cost partitioning admissibly combines the information from
multiple heuristics for state-space search. We use a greedy
method called saturated cost partitioning that considers the
heuristics in sequence and assigns the minimal fraction of the
remaining costs that it needs to preserve the heuristic estimates.
In this work, we address the problem of using more
expressive transition cost functions with saturated cost partitioning
to obtain stronger heuristics. Our contribution is
subset-saturated transition cost partitioning that combines the
concepts of using transition cost functions and prioritizing
states that look more important during the search. Our empirical
evaluation shows that this approach still causes too much
computational overhead but leads to more informed heuristics.
-
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.
-
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.
-
David Speck, Florian Geißer and Robert Mattmüller.
When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search.
In
Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263-271.
2020.
(Show abstract)
(Hide abstract)
(PDF)
Symbolic search has proven to be a competitive approach to cost-optimal
planning, as it compactly represents sets of states by symbolic data
structures.
While heuristics for symbolic search exist, symbolic bidirectional
blind search empirically outperforms its heuristic counterpart and is
therefore the dominant search strategy.
This prompts the question of why heuristics do not seem to pay off in symbolic
search. As a first step in answering this question, we investigate the search
behaviour of symbolic heuristic search by means of BDDA*.
Previous work identified the partitioning of state sets
according to their heuristic values as the main bottleneck.
We theoretically and empirically evaluate the search behaviour of BDDA*
and reveal another fundamental problem: we prove that the use of a heuristic
does not always improve the search performance of BDDA*. In general, even
the perfect heuristic can exponentially deteriorate search performance.
-
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.
-
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.
-
Sumitra Corraya, Florian Geißer, David Speck and Robert Mattmüller.
An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning.
In
Proceedings of the 42nd German Conference on Artificial Intelligence
(KI 2019), pp. 123-130.
2019.
(Show abstract)
(Hide abstract)
(PDF)
(PDF; Online)
The vast majority of work in planning to date has focused on state-independent action costs. However, if a planning task features state-dependent costs, using a cost model with state-independent costs means either introducing a modeling error, or potentially sacrificing compactness of the model. In this paper, we investigate the conflicting priorities of modeling accuracy and compactness empirically, with a particular focus on the extent of the negative impact of reduced modeling accuracy on (a) the quality of the resulting plans, and (b) the search guidance provided by heuristics that are fed with inaccurate cost models. Our empirical results show that the plan suboptimality introduced by ignoring state-dependent costs can range, depending on the domain, from inexistent to several orders of magnitude. Furthermore, our results show that the impact on heuristic guidance additionally depends strongly on the heuristic that is used, the specifics of how exactly the costs are represented, and whether one is interested in heuristic accuracy, node expansions, or overall runtime savings.
-
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.
-
David Speck, Florian Geißer, Robert Mattmüller and Álvaro Torralba.
Symbolic Planning with Axioms.
In
Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464-572.
2019.
(Show abstract)
(Hide abstract)
(PDF)
Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in cost-optimal classical planning with axioms.
-
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.
-
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.
-
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.
-
David Speck, Florian Geißer and Robert Mattmüller.
Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams.
In
Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
(technical report with proofs; PDF)
Symbolic representations have attracted significant attention in optimal
planning. Binary Decision Diagrams (BDDs) form the basis for symbolic search
algorithms. Closely related are Algebraic Decision Diagrams (ADDs), used to
represent heuristic functions.
Also, progress was made in dealing with models that take state-dependent
action costs into account. Here, costs are represented as Edge-valued
Multi-valued Decision Diagrams (EVMDDs), which can be exponentially more
compact than the corresponding ADD representation. However, they were not
yet considered for symbolic planning.
In this work, we study EVMDD-based symbolic search for optimal planning. We
define EVMDD-based representations of state sets and transition relations,
and show how to compute the necessary operations required for EVMDD-A*. This
EVMDD-based version of symbolic A* generalizes its BDD variant, and allows
to solve planning tasks with state-dependent action costs.
We prove theoretically that our approach is sound, complete and optimal.
Additionally, we present an empirical analysis comparing EVMDD-A* to BDD-A*
and explicit A* search. Our results underscore the usefulness of symbolic
approaches and the feasibility of dealing with models that go beyond unit
costs.
-
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.
-
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.
-
David Speck, Florian Geißer and Robert Mattmüller.
SYMPLE: Symbolic Planning based on EVMDDs.
In
The 9th International Planning Competition (IPC 2018), pp. 82-85.
2018.
(Show abstract)
(Hide abstract)
(PDF)
SYMPLE is a classical planner which performs bidirectional
symbolic search. Symbolic search has proven to be a useful
approach to optimal classical planning and is usually based on
Binary Decision Diagrams (BDDs). Our approach is based on
an alternative data structure called Edge-valued Multi-valued
Decision Diagrams (EVMDDs), which have some structural
advantages over BDDs.
-
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.
-
Benedict Wright and Robert Mattmüller.
Automated Data Management Workflow Generation with Ontologies and Planning.
In
Proceedings of the 30th Workshop on Planen/Scheduling und Konfigurieren/Entwerfen (PUK 2016).
2016.
(PDF)
-
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.
-
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.
-
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract).
In
Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by partitioning action costs among the abstractions. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of state-dependent cost partitionings with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it can sometimes improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning.
-
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning.
In
Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Abstractions for Planning with State-Dependent Action Costs.
In
Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Extending the classical planning formalism with state-dependent action
costs (SDAC) allows an up to exponentially more compact task encoding.
Recent work proposed to use edge-valued multi-valued decision diagrams
(EVMDDs) to represent cost functions, which allows to automatically detect
and exhibit structure in cost functions and to make heuristic estimators
accurately reflect SDAC. However, so far only the inadmissible additive
heuristic has been considered in this context. In this paper, we define
informative admissible abstraction heuristics which enable optimal
planning with SDAC. We discuss how abstract cost values can be extracted
from EVMDDs that represent concrete cost functions without adjusting them
to the selected abstraction. Our theoretical analysis shows that this is
efficiently possible for abstractions that are Cartesian or coarser. We
adapt the counterexample-guided abstraction refinement approach to derive
such abstractions. An empirical evaluation of the resulting heuristic
shows that highly accurate values can be computed quickly.
-
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.
-
Johannes Aldinger, Robert Mattmüller and Moritz Göbelbecker.
Complexity Issues of Interval Relaxed Numeric Planning.
In
KI 2015: Advances in Artificial Intelligence
(KI 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Automated planning is computationally hard even in its most
basic form as STRIPS planning. We are interested in numeric
planning with instantaneous actions, a problem that is not
decidable in general. Relaxation is an approach to simplifying
complex problems in order to obtain guidance in the original
problem. We present a relaxation approach with intervals for
numeric planning and show that plan existence can be decided
in polynomial time for tasks where dependencies between
numeric effects are acyclic.
-
David Speck, Manuela Ortlieb and Robert Mattmüller.
Necessary Observations in Nondeterministic Planning.
In
Proceedings of the 38th German Conference on Artificial Intelligence
(KI 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
An agent that interacts with a nondeterministic environment can
often only partially observe the surroundings. This necessitates
observations via sensors rendering more information about the
current world state. Sensors can be expensive in many regards
therefore it can be essential to minimize the amount of sensors
an agent requires to solve given tasks. A limitation for sensor
minimization is given by essential sensors which are always
required to solve particular problems. In this paper we present
an efficient algorithm which determines a set of necessary observation
variables. More specifically, we develop a bottom-up algorithm which
computes a set of variables which are always necessary to observe,
in order to always reach a goal state. Our experimental results show
that the knowledge about necessary observation variables can be used
to minimize the number of sensors of an agent.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In
Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Most work in planning focuses on tasks with state-independent or
even uniform action costs. However, supporting state-dependent
action costs admits a more compact representation of many
tasks. We investigate how to solve such tasks using heuristic
search, with a focus on delete-relaxation heuristics. We first
define a generalization of the additive heuristic to such tasks
and then discuss different ways of computing it via compilations
to tasks with state-independent action costs and more directly
by modifying the relaxed planning graph. We evaluate these
approaches theoretically and present an implementation of the
generalized additive heuristic for planning with state-dependent
action costs. To our knowledge, this gives rise to the first
approach able to handle even the hardest instances of the
combinatorial Academic Advising domain from the International
Probabilistic Planning Competition (IPPC) 2014.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In
Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015).
2015.
Extended abstract of the IJCAI 2015 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Supporting state-dependent action costs in planning admits a
more compact representation of many tasks. We generalize the
additive heuristic and compute it by embedding decision-diagram
representations of action cost functions into the RPG. We give a
theoretical evaluation and present an implementation of the
generalized additive heuristic. This allows us to handle even
the hardest instances of the combinatorial Academic Advising
domain from the IPPC 2014.
-
Johannes Aldinger, Robert Mattmüller and Moritz Göbelbecker.
Complexity Issues of Interval Relaxed Numeric Planning.
In
Proceedings of the ICAPS-2015 Workshop on Heuristic and Search for Domain-Independent Planning (HSDIP 2015).
2015.
Superseded by the KI 2015 paper of the same name..
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Automated planning is a hard problem even in its most basic form
as STRIPS planning. We are interested in numeric planning tasks
with instantaneous actions, a problem which is not even
decidable in general. Relaxation is an approach to simplifying
complex problems in order to obtain guidance in the original
problem. In this paper we present a relaxation approach with
intervals for numeric planning and discuss the arising
complexity issues.
-
Thorsten Engesser, Thomas Bolander, Robert Mattmüller and Bernhard Nebel.
Cooperative Epistemic Multi-Agent Planning With Implicit Coordination.
In
Proceedings of the ICAPS-2015 Workshop on Distributed and Multi-Agent Planning (DMAP 2015).
2015.
Superseded by the M4M 2017 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Epistemic Planning has been used to achieve ontic and epistemic
control in multi-agent situations. We extend the formalism to
include perspective shifts, allowing us to define a class of
cooperative problems in which both action planning and execution
is done in a purely distributed fashion, meaning coordination is
only allowed implicitly by means of the available epistemic
actions. While this approach can be fruitfully applied to model
reasoning in some simple social situations, we also provide some
benchmark applications to show that the concept is useful for
multi-agent systems in practice.
-
Jonas Thiem, Robert Mattmüller and Manuela Ortlieb.
Counterexample-Guided Abstraction Refinement for POND Planning.
In
Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Counterexample-guided abstraction refinement (CEGAR) allows to
gradually refine a problem definition until the required detail
for a solution is present. We propose the use of CEGAR to
demonstrate unsolvability of a planning problem while avoiding a
search through the whole state space. This allows a sensor
minimization algorithm for partially observable
non-deterministic (POND) planning problems to determine the
definitive unsolvability notably faster, which is a necessary
part of current approaches of computing the minimal sensor
variable set. We determine from our empirical results that while
the presented algorithm causes some slowdown for solvable
problems, the unsolvability is determined at a much greater
speed with this novel approach.
-
Dominik Winterer, Robert Mattmüller and Martin Wehrle.
Stubborn Sets for Fully Observable Nondeterministic Planning.
In
Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The stubborn set method is a state-space reduction technique,
originally introduced in model checking and then transfered to
classical planning. It was shown that stubborn sets
significantly improve the performance of optimal deterministic
planners by considering only a subset of applicable operators in
a state. Fully observable nondeterministic planning (FOND)
extends the formalism of classical planning by nondeterministic
operators. We show that stubborn sets are also beneficial for
FOND problems. We introduce nondeterministic stubborn sets,
stubborn sets which preserve strong cyclic plans. We follow two
approaches: Fast Incremental Planning with stubborn sets from
classical planning and LAO* search with nondeterministic
stubborn sets. Our experiments show that both approaches
increase coverage and decrease node generations when compared to
their respective baselines.
-
Robert Mattmüller, Manuela Ortlieb and Erik Wacker.
Minimizing Necessary Observations for Nondeterministic Planning.
In
Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014).
2014.
(Show abstract)
(Hide abstract)
(PDF)
Autonomous agents interact with their environments via sensors and actuators.
Motivated by the observation that sensors can be expensive, in this paper we
are concerned with the problem of minimizing the amount of sensors an agent
needs in order to successfully plan and act in a partially observable
nondeterministic environment. More specifically, we present a simple greedy
top-down algorithm in the space of observation variables that returns an
inclusion minimal set of state variables sufficient to observe in order to
find a plan. We enhance the algorithm by reusing plans from earlier iterations
and by the use of functional dependencies between variables that allows the
values of some variables to be inferred from those of other variables. Our
experimental evaluation on a number of benchmark problems shows promising
results regarding runtime, numbers of sensors and plan quality.
-
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.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games.
In
Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 357-362.
2014.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In General Game Playing, a player receives the rules of an unknown game and
attempts to maximize his expected reward. Since 2011, the GDL-II rule language
extension allows the formulation of nondeterministic and partially observable
games. In this paper, we present an algorithm for such games, with a focus on
the single-player case. Conceptually, at each stage, the proposed Norns algorithm
distinguishes between the past, present and future steps of the game. More
specifically, a belief state tree is used to simulate a potential past that
leads to a present that is consistent with received observations. Unlike other
related methods, our method is asymptotically optimal. Moreover, augmenting the
belief state tree with iteratively improved probabilities speeds up the
process over time significantly.
As this allows a true picture of the present, we additionally present an
optimal version of the well-known UCT algorithm for partially observable
single-player games. Instead of performing hindsight optimization on a
simplified, fully observable tree, the true future is simulated on an
action-observation tree that takes partial observability into account. The
expected reward estimates of applicable actions converge towards the true
expected rewards even for moves that are only used to gather information. We
prove that our algorithm is asymptotically optimal for single-player games and
POMDPs and support our claim with an empirical evaluation.
-
Dr. Yusra Alkhazraji, Michael Katz, Robert Mattmüller, Florian Pommerening, Alexander Shleyfman and Martin Wehrle.
Metis: Arming Fast Downward with Pruning and Incremental Computation (planner abstract).
In
the 8th International Planning Competition (IPC 2014) (deterministic track).
2014.
(Show abstract)
(Hide abstract)
(PDF)
Metis is a sequential optimal planner that implements three
components on top of the Fast Downward planning system (Helmert 2006). The planner performs an A ∗ search
using the following three major components:
• an admissible incremental LM-cut heuristic (Pommeren-
ing and Helmert 2013),
• a symmetry based pruning technique (Domshlak, Katz,
and Shleyfman 2012), and
• a partial order reduction based pruning technique based
on strong stubborn sets (Wehrle and Helmert 2012).
Each of those techniques was extended to support conditional effects. In addition, Metis features a flexible invocation of partial order reduction based pruning. In what follows, we describe each of these components in detail.
-
Manuela Ortlieb and Robert Mattmüller.
Pattern-Database Heuristics for Partially Observable Nondeterministic Planning.
In
Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013).
2013.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Heuristic search is the dominant approach to classical
planning. However, many realistic problems violate classical
assumptions such as determinism of action outcomes or full
observability. In this paper, we investigate how - and how
successfully - a particular classical technique, namely informed search
using an abstraction heuristic, can be transferred to
nondeterministic planning under partial observability. Specifically,
we explore pattern-database heuristics with automatically generated
patterns in the context of informed progression search for strong
cyclic planning under partial observability. To that end, we discuss
projections and how belief states can be heuristically assessed
either directly or by going back to the contained world states, and
empirically evaluate the resulting heuristics internally and
compared to a delete-relaxation and a blind approach.
From our experiments we can conclude that in terms of
guidance, it is preferable to represent both nondeterminism and
partial observability in the abstraction (instead of relaxing them),
and that the resulting abstraction heuristics significantly
outperform both blind search and a delete-relaxation approach where
nondeterminism and partial observability are also relaxed.
-
Martin Wehrle, Malte Helmert, Dr. Yusra Alkhazraji and Robert Mattmüller.
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core.
In
Proceedings of the 23rd International Conference on
Automated Planning and Scheduling (ICAPS13).
2013.
(Show abstract)
(Hide abstract)
(PDF)
In the last years, pruning techniques based on partial order reduction have
found increasing attention in the planning community. One recent result is
that the expansion core method is a special case of the strong stubborn sets
method proposed in model checking. However, it is still an open question if
there exist efficiently computable strong stubborn sets with strictly
higher pruning power than expansion core. In this paper, we prove that the
pruning power of strong stubborn sets is strictly higher than the pruning
power of expansion core even for a straight-forward instantiation of strong
stubborn sets. This instantiation is as efficiently computable as expansion
core. Hence, our theoretical results suggest that strong stubborn sets should
be preferred to expansion core. Our empirical evaluation on all optimal
benchmarks from the international planning competitions up to 2011 supports
the theoretical results.
-
Dr. Yusra Alkhazraji, Martin Wehrle, Robert Mattmüller and Malte Helmert.
A Stubborn Set Algorithm for Optimal Planning.
In
Proceedings of the 20th European Conference on
Artificial Intelligence (ECAI 2012).
2012.
(Show abstract)
(Hide abstract)
(PDF)
We adapt a partial order reduction technique based on stubborn
sets, originally proposed for detecting dead ends in Petri Nets,
to the setting of optimal planning. We demonstrate that stubborn
sets can provide significant state space reductions on standard
planning benchmarks, outperforming the expansion core method.
-
Hans-Jörg Peter, Rüdiger Ehlers and Robert Mattmüller.
Synthia: Verification and Synthesis for Timed Automata.
In
Proceedings of the 23rd International Conference on Computer Aided Verification
(CAV 2011), pp. 649-655.
Springer-Verlag 2011.
(Show abstract)
(Hide abstract)
(PDF)
We present Synthia, a new tool for the verification and
synthesis of open real-time systems modeled as timed
automata. The key novelty of Synthia is the underlying
abstraction refinement approach that combines the efficient
symbolic treatment of timing information by difference bound
matrices (DBMs) with the usage of binary decision diagrams
(BDDs) for the discrete parts of the system description. Our
experiments show that the analysis of both closed and open
systems greatly benefits from identifying large relevant and
irrelevant system parts on coarse abstractions early in the
solution process. Synthia is licensed under the GNU GPL and
available from our website.
-
Rüdiger Ehlers, Robert Mattmüller and Hans-Jörg Peter.
Combining Symbolic Representations for Solving Timed Games.
In
Proceedings of the 8th International Conference on Formal Modelling and Analysis of Timed Systems
(FORMATS 2010), pp. 107-121.
Springer-Verlag 2010.
(Show abstract)
(Hide abstract)
(PDF)
We present a general approach to combine symbolic state space
representations for the discrete and continuous parts in the
synthesis of winning strategies for timed reachability
games. The combination is based on abstraction refinement
where discrete symbolic techniques are used to produce a
sequence of abstract timed game automata. After each
refinement step, the resulting abstraction is used for
computing an under- and an over-approximation of the timed
winning states. The key idea is to identify large relevant and
irrelevant parts of the precise weakest winning strategy
already on coarse, and therefore simple, abstractions. If
neither the existence nor nonexistence of a winning strategy
can be established in the approximations, we use them to guide
the refinement process. Based on a prototype that combines
binary decision diagrams and difference bound matrices, we
experimentally evaluate the technique on standard benchmarks
from timed controller synthesis. The results clearly
demonstrate the potential of the new approach concerning
running time and memory consumption compared to the classical
on-the-fly algorithm implemented in UPPAAL-Tiga.
-
J. Benton, Kartik Talamadupula, Patrick Eyerich, Robert Mattmüller and Subbarao Kambhampati.
G-value Plateaus: A Challenge for Planning.
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. 259-262.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Recent years have seen the development of several scalable
planners, many of which follow the string of successes found
in using heuristic, best-first search methods. While this
provides positive reinforcement for continuing work along
these lines, fundamental problems arise when handling
objectives whose value does not change with each search
operation. An extreme case of this occurs when handling the
objective of generating a temporal plan with short
makespan. Typically used heuristic search methods assume
strictly positive edge costs for their guarantees on
completeness and optimality to hold, while the usual
"fattening" and "advance time" steps of heuristic search
algorithms for temporal planning have the potential for
zero-cost edges, resulting in "g-value plateaus". In this
paper we point out some underlying difficulties with using
modern heuristic search methods for optimizing makespan and
discuss how the presence of these problems contributes to the
poor performance of makespan-optimizing heuristic search
planners. To further illustrate this, we show empirical
results on recent benchmarks using a planner made with
makespan optimization in mind.
-
Robert Mattmüller, Manuela Ortlieb, Malte Helmert and Pascal Bercher.
Pattern Database Heuristics for Fully Observable Nondeterministic Planning.
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. 105-112.
AAAI Press 2010.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(BIB)
When planning in an uncertain environment, one is often
interested in finding a contingent plan that prescribes
appropriate actions for all possible states that may be
encountered during the execution of the plan. We consider the
problem of finding strong and strong cyclic plans for fully
observable nondeterministic (FOND) planning problems. The
algorithm we choose is LAO*, an informed explicit state search
algorithm. We investigate the use of pattern database (PDB)
heuristics to guide LAO* towards goal states. To obtain a
fully domain-independent planning system, we use an automatic
pattern selection procedure that performs local search in the
space of pattern collections. The evaluation of our system on
the FOND benchmarks of the Uncertainty Part of the
International Planning Competition 2008 shows that our
approach is competitive with symbolic regression search in
terms of problem coverage and speed.
-
Hans-Jörg Peter and Robert Mattmüller.
Component-based Abstraction Refinement for
Timed Controller Synthesis.
In
Theodore P. Baker (ed.),
Proceedings of the 30th IEEE Real-Time Systems Symposium
(RTSS 2009), pp. 364-374.
IEEE Computer Society 2009.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
We present a novel technique for synthesizing controllers for
distributed real-time environments with safety requirements.
Our approach is an abstraction refinement extension to the
on-the-fly algorithm by Cassez et al. from 2005. Based on
partial compositions of some environment components, each
refinement cycle constructs a sound abstraction that can be
used to obtain under- and over-approximations of all valid
controller implementations. This enables (1) early
termination if an implementation does not exist in the
over-approximation, or, if one does exist in the
under-approximation, and (2) pruning of irrelevant moves in
subsequent refinement cycles. In our refinement loop, the
precision of the abstractions incrementally increases and
converges to all specification-critical components.
We implemented our approach in a prototype synthesis tool and
evaluated it on an industrial benchmark. In comparison with
the timed game solver UPPAAL-Tiga, our technique outperforms
the nonincremental approach by an order of magnitude.
-
Patrick Eyerich, Robert Mattmüller and Gabriele Röger.
Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning.
In
Proceedings of the 19th International Conference on Automated
Planning and Scheduling (ICAPS 2009), pp. 130-137.
AAAI Press 2009.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(BIB)
Planning systems for real-world applications need the ability
to handle concurrency and numeric fluents. Nevertheless, the
predominant approach to cope with concurrency followed by the
most successful participants in the latest International
Planning Competitions (IPC) is still to find a sequential plan
that is rescheduled in a post-processing step. We present
Temporal Fast Downward (TFD), a planning system for temporal
problems that is capable of finding low-makespan plans by
performing a heuristic search in a temporal search space. We
show how the context-enhanced additive heuristic can be
successfully used for temporal planning and how it can be
extended to numeric fluents. TFD often produces plans of high
quality and, evaluated according to the rating scheme of the
last IPC, outperforms all state-of-the-art temporal planning
systems.
-
Pascal Bercher and Robert Mattmüller.
Solving Non-deterministic Planning Problems with
Pattern Database Heuristics.
In
B. Mertsching, M. Hund and Z. Aziz (eds.),
Proceedings of the 32nd Annual Conference on Artificial
Intelligence (KI 2009), pp. 57-64.
Springer-Verlag 2009.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(BIB)
Non-determinism arises naturally in many real-world
applications of action planning. Strong plans for this type of
problems can be found using AO* search guided by an
appropriate heuristic function. Most domain-independent
heuristics considered in this context so far are based on the
idea of ignoring delete lists and do not properly take the
non-determinism into account. Therefore, we investigate the
applicability of pattern database (PDB) heuristics to
non-deterministic planning. PDB heuristics have emerged as
rather informative in a deterministic context. Our empirical
results suggest that PDB heuristics can also perform
reasonably well in non-deterministic planning. Additionally,
we present a generalization of the pattern additivity
criterion known from classical planning to the
non-deterministic setting.
-
Pascal Bercher and Robert Mattmüller.
A Planning Graph Heuristic for Forward-Chaining Adversarial Planning.
In
Proceedings of the 18th European Conference on
Artificial Intelligence (ECAI
2008), pp. 921-922.
IOS Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(poster; PDF)
(BIB)
In contrast to classical planning, in adversarial planning, the
planning agent has to face an adversary trying to prevent him from reaching
his goals. In this paper, we investigate a forward-chaining approach to
adversarial planning based on the AO* algorithm. The exploration of the
underlying AND/OR graph is guided by a heuristic evaluation function,
inspired by the relaxed planning graph heuristic used in the FF
planner. Unlike FF, our heuristic uses an adversarial planning graph with
distinct proposition and action layers for the protagonist and antagonist.
First results suggest that in certain planning
domains, our approach yields results competitive with the state of the art.
-
Malte Helmert and Robert Mattmüller.
Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI 2008), pp. 938-943.
AAAI Press 2008.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(BIB)
The efficiency of optimal planning algorithms based on heuristic
search crucially depends on the accuracy of the heuristic
function used to guide the search. Often, we are interested in
domain-independent heuristics for planning. In order to assess the
limitations of domain-independent heuristic planning, it appears
interesting to analyse the (in)accuracy of common
domain-independent planning heuristics in the IPC benchmark
domains. For a selection of these domains, we analytically
investigate the accuracy of the h+
heuristic, the hm family of heuristics, and
certain (additive) pattern database heuristics, compared to the
perfect heuristic h*. Whereas
h+ and additive pattern database heuristics
usually return cost estimates proportional to the true cost,
non-additive hm and non-additive
pattern-database heuristics can yield results underestimating
the true cost by arbitrarily large factors.
-
Malte Helmert and Robert Mattmüller.
On the Accuracy of Admissible Heuristic Functions in
Selected Planning Domains.
In
Proceedings of the
ICAPS-2007
Workshop on Heuristics for Domain-independent Planning: Progress,
Ideas, Limitations, Challenges.
2007.
Superseded by the AAAI 2008 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
The efficiency of optimal planning algorithms based on heuristic
search crucially depends on the accuracy of the heuristic
function used to guide the search. Often, we are interested in
domain-independent heuristics for planning. In assessing the
limitations of domain-independent heuristic planning, it appears
interesting to analyse the (in)accuracy of common
domain-independent planning heuristics in the IPC benchmark
domains. For a selection of these domains, we analytically
investigate the accuracy of the h+
heuristic, the hk family of heuristics, and
certain (additive) pattern database heuristics, compared to the
optimal heuristic h*. Whereas
h+ and additive pattern database heuristics
usually return cost estimates proportional to the true cost,
non-additive hk and non-additive
pattern-database heuristics can yield results underestimating
the true cost by arbitrarily large factors.
-
Robert Mattmüller and Jussi Rintanen.
Planning for Temporally Extended Goals as Propositional Satisfiability.
In
Proceedings of the 20th International Joint Conference on Artificial Intelligence
(IJCAI 2007), pp. 1966-1971.
2007.
(Show abstract)
(Hide abstract)
(PDF)
(PS.GZ)
(poster; PDF)
(BIB)
Planning for temporally extended goals (TEGs) expressed as formulae of
Linear-time Temporal Logic (LTL) is a proper generalization of classical
planning, not only allowing to specify properties of a goal state but of
the whole plan execution. Additionally, LTL formulae can be used to represent
domain-specific control knowledge to speed up planning. In this paper we
extend SAT-based planning for LTL goals (akin to bounded LTL model-checking
in verification) to partially ordered plans, thus significantly increasing
planning efficiency compared to purely sequential SAT planning. We consider
a very relaxed notion of partial ordering and show how planning for LTL
goals (without the next-time operator) can be translated into a SAT problem
and solved very efficiently. The results extend the practical applicability of
SAT-based planning to a wider class of planning problems. In addition, they
could be applied to solving problems in bounded LTL model-checking more
efficiently.
-
Malte Helmert, Robert Mattmüller and Sven Schewe.
Selective Approaches for Solving Weak Games.
In
Proceedings of the Fourth International Symposium on
Automated Technology for Verification and Analysis (ATVA 2006), pp. 200-214.
Springer-Verlag 2006.
(Show abstract)
(Hide abstract)
(PDF)
Model-checking alternating-time properties has recently
attracted much interest in the verification of distributed
protocols. While checking the validity of a specification in
alternating-time temporal logic (ATL) against an explicit
model is cheap (linear in the size of the formula and the
model), the problem becomes EXPTIME-hard when symbolic
models are considered. Practical ATL model-checking therefore
often consumes too much computation time to be tractable.
In this paper, we describe a novel approach for ATL
model-checking, which constructs an explicit weak model-checking
game on-the-fly. This game is then evaluated using heuristic
techniques inspired by efficient evaluation algorithms for
and/or-trees.
To show the feasibility of our approach, we compare its
performance to the ATL model-checking system MOCHA on some
practical examples. Using very limited heuristic guidance, we
achieve a significant speedup on these benchmarks.
-
Malte Helmert, Robert Mattmüller and Gabriele Röger.
Approximation Properties of Planning Benchmarks.
In
Proceedings of the 17th European Conference on Artificial
Intelligence (ECAI 2006), pp. 585-589.
2006.
(Show abstract)
(Hide abstract)
(PDF)
For many classical planning domains, the computational complexity of
non-optimal and optimal planning is known. However, little is known
about the area in between the two extremes of finding some plan
and finding optimal plans. In this contribution, we provide a
complete classification of the propositional domains from the first four
International Planning Competitions with respect to the approximation
classes PO, PTAS, APX, poly-APX, and NPO.
-
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|.
-
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.
-
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.
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.
-
Klaus René Garcia Rosas, Martin Zimmer and Bernhard Nebel.
Deep Learning vs. Classical Model-Based Fault Detection in Industrial Heating-Cooling Systems.
In
32nd International Workshop on Principle of Diagnosis DX-2021).
2021.
(Show abstract)
(Hide abstract)
(Online; PDF)
Faults in heating-cooling systems can often be observed by changes in temperature. Such faults can be detected and identified by modeling thermo-dynamic behavior. In classical models, physical equations with fixed or trainable parameters are used to model this behavior. They are limited in non-linear complexity and the number of parameters to be estimated. They also usually require the involvement of expert knowledge. In this paper, a deep learning approach is presented for modeling thermodynamic behavior without explicitly modeling the physical properties. The modeled artificial neural network (ANN) can predict the tem- perature based on other influencing variables. A comparison with a mathematical-physical model (MM) shows that the ANN can reproduce temperature changes similarly good when sufficiently data is available. With increasing prediction windows, the ANN even outperformed the MM model for most states. Both models can detect certain heating faults by comparing the measured and predicted temperatures. Finally, we demonstrate the diagnostic capabilities of our methods by injecting a fault into the system.
-
David Speck, David Borukhson, Robert Mattmüller and Bernhard Nebel.
On the Compilability and Expressive Power of State-Dependent Action Costs.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358-366.
2021.
(Show abstract)
(Hide abstract)
(PDF)
While state-dependent action costs are practically relevant and have been
studied before, it is still unclear if they are an essential feature of planning
tasks.
In this paper, we study to what extent state-dependent action costs are an
essential feature by analyzing under which circumstances they can be compiled away.
We give a comprehensive classification for combinations of action cost functions and possible
cost measures for the compilations.
Our theoretical results show that if both task sizes and plan lengths are to be
preserved polynomially, then the boundary between compilability and
non-compilability lies between FP and FPSPACE computable action cost
functions (under a mild assumption on the polynomial hierarchy). Preserving task
sizes polynomially and plan lengths linearly at the same time is impossible.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Michael Thielscher.
Game description language and dynamic epistemic logic compared.
Artificial Intelligence 292. 2021.
(Show abstract)
(Hide abstract)
(Online; DOI)
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). 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 translations between those fragments of GDL-III and DEL.
-
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.
-
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.
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.
-
Thorsten Engesser, Thomas Bolander, Robert Mattmüller and Bernhard Nebel.
Cooperative Epistemic Multi-Agent Planning With Implicit Coordination.
In
Proceedings of the ICAPS-2015 Workshop on Distributed and Multi-Agent Planning (DMAP 2015).
2015.
Superseded by the M4M 2017 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Epistemic Planning has been used to achieve ontic and epistemic
control in multi-agent situations. We extend the formalism to
include perspective shifts, allowing us to define a class of
cooperative problems in which both action planning and execution
is done in a purely distributed fashion, meaning coordination is
only allowed implicitly by means of the available epistemic
actions. While this approach can be fruitfully applied to model
reasoning in some simple social situations, we also provide some
benchmark applications to show that the concept is useful for
multi-agent systems in practice.
-
Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
On qualitative route descriptions: Representation, agent models, and computational complexity.
Journal of Philosophical Logic 44 (2), pp. 177-201. 2015.
(Show abstract)
(Hide abstract)
(Online; DOI)
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 and discuss which
agent models can be translated into PDL programs. 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.
-
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.
-
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.
-
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.
-
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)
