Publikationen

Vollständige Liste der Publikationen

Aktuelle Veröffentlichungen (letzte 12 Monate):

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

Felix Lindner, Robert Mattmüller und Bernhard Nebel.
Moral Permissibility of Action Plans.
In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). 2019.
(PDF)
Thomas Bolander, Thorsten Engesser, Robert Mattmüller und 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), S. 445-453. 2018.
(Abstract einblenden) (Abstract ausblenden) (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 und Bernhard Nebel.
Compiling Away Soft Trajectory Constraints in Planning.
In Proceedings of the Sixteenth COnference on Principles of Knowledge Representation and Reasoning (KR18), S. 474-482. 2018.
(Abstract einblenden) (Abstract ausblenden) (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 und 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), S. 876-881. 2018.
(Abstract einblenden) (Abstract ausblenden) (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 und 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.
(Abstract einblenden) (Abstract ausblenden) (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.
Laura Wächter und Felix Lindner.
An Explorative Comparison of Blame Attributions to Companion Robots Across Various Moral Dilemmas.
In Proceedings of The 6th International Conference on Human-Agent Interaction (HAI 2018). 2018.
Barbara Kuhnert, Felix Lindner, Martin Mose Bentzen und Marco Ragni.
Causal Structure of Moral Dilemmas Predicts Perceived Difficulty of Making a Decision.
In Proceedings of the KogWis 2018 (Extended Abstract). 2018.
Martin Mose Bentzen, Felix Lindner, Louise Dennis und Michael Fisher.
Moral Permissibility of Actions in Smart Home Systems.
In Proceedings of the FLoC 2018 Workshop on Robots, Morality, and Trust through the Verification Lens (Extended Abstract). 2018.
Tim Schulte.
Stubborn Sets Pruning for Privacy Preserving Planning.
In Proceedings of the Eleventh Annual Symposium on Combinatorial Search (SoCS 2018) (SoCS 2018). 2018.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We adapt a partial-order reduction technique based on stubborn sets to the setting of privacy-preserving multi-agent planning. We prove that the presented approach preserves optimality and show experimentally that it can significantly improve search performance on some domains.
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel und Michael Thielscher.
Game Description Language and Dynamic Epistemic Logic Compared.
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2018), S. 1795-1802. 2018.
(Abstract einblenden) (Abstract ausblenden) (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.
Hanna Stellmach und Felix Lindner.
Perception of an Uncertain Ethical Reasoning Robot: A Pilot Study.
In Proceedings of Mensch und Computer 2018. 2018.
(Abstract einblenden) (Abstract ausblenden)

The study investigates the effect of uncertainty expressed by a robot facing a moral dilemma. Participants (N = 80) were shown a video of a robot explaining a moral dilemma and the decision it makes. The robot either expressed certainty or uncertainty about its decision. Participants rated how much blame the robot deserves for its action, the moral wrongness of the action, and their impression of the robot in terms of four scale dimensions measuring social perception. The results suggest that participants that were not familiar with the moral dilemma assign more blame to the robot for the same action when it expresses uncertainty, while expressed uncertainty has less effect on moral wrongness judgments. There was no significant effect of expressed uncertainty on participants’ impression of the robot. We discuss implications of this result for the design of social robots.
David Speck, Florian Geißer und 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.
(Abstract einblenden) (Abstract ausblenden) (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.
Tim Schulte.
Stubborn Sets Pruning for Privacy Preserving Planning.
In Proceedings of the 5th Workshop on Distributed and Multi-Agent Planning (DMAP 2018) (DMAP 2018). 2018.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We adapt a partial-order reduction technique based on stubborn sets to the setting of privacy-preserving multi-agent planning. We prove that the presented approach preserves optimality and show experimentally that it can significantly improve search performance on some domains.
Benedict Wright, Robert Mattmüller und Bernhard Nebel.
Compiling Away Soft Trajectory Constraints in Planning.
In Proceedings of the Workshop on Knowledge Engineering for Planning and Scheduling (KEPS18), S. 38-45. 2018.
(Abstract einblenden) (Abstract ausblenden) (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 und Sebastian Sardiña.
Plan Relaxation via Action Debinding and Deordering.
In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS 2018), S. 278-287. 2018.
(Abstract einblenden) (Abstract ausblenden) (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 und Martin Mose Bentzen.
A Formalization of Kant's Second Formulation of the Categorical Imperative.
In Proceedings of the 14th International Conference on Deontic Logic and Normative Systems (DEON). 2018.
(Abstract einblenden) (Abstract ausblenden)

We present a formalization and computational implementation of the second formulation of Kant's categorical imperative. This ethical principle requires an agent to never treat someone merely as a means but always also as an end. Here we interpret this principle in terms of how persons are causally affected by actions. We introduce Kantian causal agency models in which moral patients, actions, goals, and causal influence are represented, and we show how to formalize several readings of Kant's categorical imperative that correspond to Kant's concept of strict and wide duties towards oneself and others. Stricter versions handle cases where an action directly causally affects oneself or others, whereas the wide version maximizes the number of persons being treated as an end. We discuss limitations of our formalization by pointing to one of Kant's cases that the machinery cannot handle in a satisfying way.
Felix Lindner, Robert Mattmüller und Bernhard Nebel.
Moral Permissibility of Action Plans.
In Proceedings of the ICAPS Workshop on EXplainable AI Planning (XAIP). 2018.
(Abstract einblenden) (Abstract ausblenden) (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.
Florian Geißer und David Speck.
PROST-DD - Utilizing Symbolic Classical Planning in THTS.
In The 6th International Probabilistic Planning Competition (IPPC 2018). 2018.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We describe PROST-DD, our submission to the International Probabilistic Planning Competition 2018. Like its predecessor PROST, which already participated with success at the previous IPPC, PROST-DD is based on the trial-based heuristic tree search framework and applies the UCT* algorithm. The novelty of our submission is the heuristic used to initialize newly encountered decision nodes. We apply an iterative symbolic backward planning approach based on the determinized task. Similarly to the SPUDD approach and recent work in symbolic planning with state-dependent action costs, we encode costs and reachability of states in a single decision diagram. During initialization, these diagrams are then used to query a state for its estimated expected reward. One benefit of this heuristic is that we can optionally interweave the standard heuristic of PROST, the IDS heuristic.
David Speck, Florian Geißer und Robert Mattmüller.
SYMPLE: Symbolic Planning based on EVMDDs.
In The 9th International Planning Competition (IPC 2018), S. 82-85. 2018.
(Abstract einblenden) (Abstract ausblenden) (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.