Automated Planning and Diagnosis

The Automated Planning and Diagnosis (APD) group is part of the Knowledge Processing Laboratory (KPLAB) in the Artificial Intelligence and Integrated Computer Systems (AIICS) Division at the Department of Computer and Information Science at Linköping University.

Our research focuses on the pragmatic use of automated planning and diagnosis techniques to solve real-world problems. We view task planning as a central component of a solution that also involves essential tasks such as information gathering, motion planning, plan execution, execution monitoring, and interaction with human operators through mixed initiative interfaces. Within this larger context, areas of specific long-term interest include the following:

• Studying the integration and interaction between different aspects of the planning and execution process, including the combination of task planning and motion planning as well as the use of task planning in combination with plan execution mechanisms, execution monitoring systems, and failure diagnosis / recovery.
• Generating plans for multiple agents and cooperative systems, including delegation of subplans or subgoals and the use of distributed planning.
• Increasing the expressivity of plan representation languages and planners for these languages in order to facilitate the specification of planning domains, allow richer constraints on valid solutions, and make full use of available execution capabilities.
• Handling uncertainty and incomplete information, both in terms of timing and in terms of knowledge about the world in which an agent operates.
• Improving planning performance, both through purely algorithmic improvements and through allowing new forms of domain information to be specified and taken advantage of during the planning process.
• Studying the use of planning for diagnosis and troubleshooting, where planning techniques are used to determine which steps to take to gather the necessary information and to repair a system or otherwise recover from failures.

Application Domains

Most of our research is grounded in the pragmatic requirements of the following concrete application domains:

• Mission planning for unmanned aerial vehicles. Together with other groups at AIICS, we are involved in a long-term research endeavor involving the design, specification and implementation of autonomous architectures for intelligent unmanned aircraft systems. Applications of such systems include traffic surveillance and emergency services assistance. We currently use two Yamaha RMAX helicopters as well as two micro UAVs (MAVs), and several small quad-rotor UAVs have recently been acquired for further experimentation.
• Diagnosis and troubleshooting of complex systems. In close cooperation with Scania AB, we are applying automated planning techniques to incremental diagnosis and troubleshooting for complex systems such as heavy trucks. The need to balance the cost of testing against the cost of potentially replacing non-faulty components can be modeled as an interesting form of probabilistic planning problem, where the aim is to generate a repair plan with minimal expected cost.
• Computer games. Computer games can provide a natural environment in which to apply epistemic reasoning, where agents must generate plans given incomplete information and plan for knowledge acquisition. They can also provide a suitable testing ground for planning in the presence of agents that cannot be completely controlled by the planner, aiding research in the areas of cooperation and delegation. A small dialog-based adventure game is currently used as one method for validating research in the Logical Agents project.