Michael Brenner – Publications

(Show all abstracts) (Hide all abstracts)

2010

Marc Hanheide, Nick Hawes, Jeremy Wyatt, Moritz Göbelbecker, Michael Brenner, Kristoffer Sjöö, Alper Aydemir, Patric Jensfelt, Hendrik Zender and Geert-Jan Kruijff.
A Framework for Goal Generation and Management.
In Proceedings of the AAAI Workshop on Goal-Directed Autonomy. 2010.
(Show abstract) (Hide abstract) (BIB)

Goal-directed behaviour is often viewed as an essential char- acteristic of an intelligent system, but mechanisms to generate and manage goals are often overlooked. This paper addresses this by presenting a framework for autonomous goal gener- ation and selection. The framework has been implemented as part of an intelligent mobile robot capable of exploring unknown space and determining the category of rooms au- tonomously. We demonstrate the efficacy of our approach by comparing the performance of two versions of our inte- grated system: one with the framework, the other without. This investigation leads us conclude that such a framework is desirable for an integrated intelligent system because it re- duces the complexity of the problems that must be solved by other behaviour-generation mechanisms, it makes goal- directed behaviour more robust in the face of a dynamic and unpredictable environments, and it provides an entry point for domain-specific knowledge in a more general system.
Michael Brenner.
Creating Dynamic Story Plots with Continual Multiagent Planning.
In Maria Fox and David Poole (eds.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 1517-1522. AAAI Press 2010.
(Show abstract) (Hide abstract) (PDF) (BIB)

An AI system that is to create a story (autonomously or in interaction with human users) requires capabilities from many subfields of AI in order to create characters that themselves appear to act intelligently and believably in a coherent story world. Specifically, the system must be able to reason about the physical actions and verbal interactions of the characters as well as their perceptions of the world. Furthermore it must make the characters act believably--i.e. in a goal-directed yet emotionally plausible fashion. Finally, it must cope with (and embrace!) the dynamics of a multiagent environment where beliefs, sentiments, and goals may change during the course of a story and where plans are thwarted, adapted and dropped all the time. In this paper, we describe a representational and algorithmic framework for modelling such dynamic story worlds, Continual Multiagent Planning. It combines continual planning (i.e. an integrated approach to planning and execution) with a rich description language for modelling epistemic and affective states, desires and intentions, sensing and communication. Analysing story examples generated by our implemented system we show the benefits of such an integrated approach for dynamic plot generation.
Michael Brenner.
Dynamic Plot Generation by Continual Multiagent Planning (extended abstract).
In Proceedings of the 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010). 2010.
(Show abstract) (Hide abstract) (PDF) (BIB)

We describe how, by modelling plot generation as a Continual Multiagent Planning process, dynamic stories can be generated in which characters not only inteleave perception, action and interaction, but in which also beliefs and motivations may change repeatedly, thus driving the plot forward.
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.
Nick Hawes, Marc Hanheide, Kristoffer Sjöö, Alper Aydemir, Patric Jensfelt, Moritz Göbelbecker, Michael Brenner, Hendrik Zender, Pierre Lison, Ivana Kruijff-Korbayov, Geert-Jan M. Kruijff and Michael Zillich.
Dora The Explorer: A Motivated Robot.
In Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010). 2010.
(Show abstract) (Hide abstract) (PDF) (BIB)

Dora the Explorer is a mobile robot with a sense of curios- ity and a drive to explore its world. Given an incomplete tour of an indoor environment, Dora is driven by internal motivations to probe the gaps in her spatial knowledge. She actively explores regions of space which she hasn't previously visited but which she expects will lead her to further unex- plored space. She will also attempt to determine the cate- gories of rooms through active visual search for functionally important objects, and through ontology-driven inference on the results of this search.

2009

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.
Geert-Jan Kruijff and Michael Brenner.
Phrasing Questions.
In AAAI Spring Symposium on Agents that Learn from Human Teachers. 2009.

2008

Michael Brenner.
Continual Collaborative Planning for Mixed-Initiative Action and Interaction.
In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008). 2008.
(Show abstract) (Hide abstract) (PDF)

Multiagent environments are often highly dynamic and only partially observable which makes deliberative action planning computationally hard. In many such environments, however, agents can take a more proactive approach and suspend planning for partial plan execution, especially for active information gathering and interaction with others. This paper presents a new algorithm for Continual Collaborative Planning (CCP) that enables agents to deliberately interleave planning, acting, perception and communication. Our implementation of CCP has been evaluated with MAPSIM, a tool that automatically generates multiagent simulations from formal multiagent planning (MAP) domains. For different such simulations, we show how CCP leads to collaborative planning and acting and, despite minimal linguistic capabilities, to fairly natural dialogues between agents.
Michael Brenner and Ivana Kruijff-Korbayova.
A Continual Multiagent Planning Approach to Situated Dialogue.
In Proceedings of the 12th Workshop on the Semantics and Pragmatics of Dialogue (LonDial 2008). 2008.
(Show abstract) (Hide abstract) (PDF)

Situated dialogue is usually tightly integrated with behavior planning, physical action and perception. This paper presents an algorithmic framework, Continual Collaborative Planning (CCP), for modeling this kind of integrated behavior and shows how CCP agents naturally blend physical and communicative actions. For experiments with conversational CCP agents we have developed MAPSIM, a software environment that can generate multiagent simulations from formal multiagent planning problems automatically. MAPSIM permits comparison of CCP-based dialogue strategies on a wide range of domains and problems without domain-specific programming. Despite their linguistic capabilities being limited MAPSIM agents can already engage in fairly realistic situated dialogues. Our ongoing work is taking this approach from simulation to real human-robot interaction.
Geert-Jan Kruijff, Michael Brenner and Nick Hawes.
Continual Planning for Cross-Modal Situated Clarification in Human-Robot Interaction.
In Proceedings of the 17th IEEE International Symposium on Robots and Human Interactive Communication (RO-MAN 2008). 2008.
(Show abstract) (Hide abstract) (PDF)

Current robots do not fully understand the world they are situated in, including what humans talk to them about. A fundamental problem in robotics is thus how a robot can clarify such a lack of understanding. This paper addresses the question of how a robot can create a plan for resolving a need for clarification. This paper characterizes situated clarification as an information need which may arise in any sensory-motoric modality interpreting the situated context of the robot, or any deliberative modality referring to that context. The paper then focuses on how, once a clarification need has been identified, the robot can create a plan in which one or more modalities are involved in resolving it. Modalities are involved on the basis of the types of information they can provide. These information types are identified in the ontologies the modalities use to interconnect their content with content of other modalities ("information fusion"). We take a continual approach to planning and execution monitoring. This provides the abiltity to re-plan depending on modality availability and success in resolving (part of) a clarification need. We illustrate our implementation of this approach with several examples from our system.
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.

2007

Michael Brenner.
Situation-Aware Interpretation, Planning and Execution of User Commands by Autonomous Robots.
In Proceedings of the 16th IEEE International Symposium on Robots and Human Interactive Communication (ROMAN 2007). Jeju, Korea 2007.
(PDF)
Nick Hawes, Aaron Sloman, Jeremy Wyatt, Michael Zillich, Henrik Jacobsson, Geert-Jan Kruijff, Michael Brenner, Gregor Berginc and Danijel Skocaj.
Towards an Integrated Robot with Multiple Cognitive Functions.
In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI 2007). Vancouver, Canada 2007.
(PDF)
Geert-Jan Kruijff and Michael Brenner.
Modelling Spatio-Temporal Comprehension in Situated Human-Robot Dialogue as Reasoning About Intentions and Plans.
In AAAI Spring Symposium on Intentions. 2007.
Michael Brenner, Nick Hawes, John Kelleher and Jeremy Wyatt.
Mediating Between Qualitative and Quantitative Representations for Task-Orientated Human-Robot Interaction.
In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI 2007). Hyderabad, India 2007.
(PDF)

2006

Michael Brenner and Bernhard Nebel.
Continual Planning and Acting in Dynamic Multiagent Environments.
In Proceedings of the International Symposium on Practical Cognitive Agents and Robots. Perth, Australia 2006.
(Show abstract) (Hide abstract) (PDF)

In highly dynamic environments, e.g. multiagent systems, finding optimal action plans is practically impossible since individual agents lack important knowledge at planning time or this knowledge has become obsolete when a plan is executed. It is often more practical in such environments to enable agents to ac- tively extend their knowledge as part of their plans and then revise their decisions in light of these update. In this paper, we describe a new principled approach to Continual Planning, i.e. the integration of Planning, Execution and Monitoring. The algorithm deliberately postpones parts of the planning process to later stages in an agent’s plan-act-monitor cycle and automatically determines when to switch back to refining or revising a partly executed plan. To evaluate our (and others’) Continual Planning techniques we have developed a simulation environment where formal MA Planning domains are not only used by planning agents but also as the basis of the simulation model such that agents can not only plan, but execute actions and perceive their environment. Our experiments show that, using continual planning techniques, deliberate action planning can be used efficiently even in complex multiagent environments.

2005

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.
Michael Brenner, Nanda Wijermans, Timo Nuessle and Bart de Boer.
Simulating and Controlling Civilian Crowds in Robocup Rescue.
In RoboCup. Osaka, Japan 2005.
Winner of the RoboCupRescue Infrastructure Competition 2005.
Michael Brenner.
Planning for Multiagent Environments: From Individual Perceptions to Coordinated Execution.
In Workshop on Multiagent Planning and Scheduling (ICAPS 2005). Monterey, USA 2005.
(PDF)

2004

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)

2003

Michael Brenner.
Multiagent Planning with Partially Ordered Temporal Plans.
In Proceedings of IJCAI'03. Acapulco, Mexico 2003.
(PDF)
Michael Brenner.
A Multiagent Planning Language.
In Workshop on PDDL (ICAPS 2003). Trento, Italy 2003.
(PDF)
Michael Brenner.
Multiagent Planning with Partially Ordered Temporal Plans.
Technical Report 190, Institut für Informatik, Albert-Ludwigs-Universität Freiburg, 2003.
(PS.GZ) (PDF)

2001

Michael Brenner.
A Formal Model for Planning with Time and Resources in Concurrent Domains.
In Workshop on Planning with Resources (IJCAI 2001). Seattle, Washington, USA 2001.
(PS.GZ)
Michael Brenner.
A Formal Model of Planning for Concurrency.
Technical Report No. 155, Institut für Informatik, Albert-Ludwigs-Universität Freiburg, 2001.
(PS.GZ)

1999

Michael Brenner.
Etablissement de Croyances Mutuelles dans le Dialogue Homme-Machine.
Master's thesis, Univ. Paris XI, Orsay, France 1999.
(PS.GZ)