Research Group on the Foundations of Artificial Intelligence

(Show all abstracts) (Hide all abstracts)

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). 2008.
  (Show abstract) (Hide abstract)
  

  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)
  

  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.
  (PDF)
  

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 No. 190, Institut für Informatik, 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, 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)