What is planning about?

Robot

Planning is about deciding what to do (i.e., goal decomposition), how to do it (resource allocation) and when to do it (scheduling). For human beings, we plan rather only in unusual situations (e.g., planning a trip or finding a route in a new city) or in tasks with a combinatorial or cognitive complexity (e.g., assembling a device). For artificial intelligence systems (e.g., robots, computer games), planning is a fundamental process of decision making in complex situations. A robot needs to plan even in environments it is familiar with because it does not have the human capability of complex intelligent reflex behaviours. In robotics and other automated systems, very simple operations that may appear reactive for human beings are often implemented through explicit deliberation processes and goal-directed behaviours are closely linked to planning processes. This is one of the reasons why planning remains at the core of artificial intelligence research whereas for humans it remains for the most part a cognitive capability useful only in solving complex tasks. From a pure algorithmic perspective, many planning problems overlap with problems in the areas of operational research scheduling and automatic control.

What kinds of planning problems do we deal with?

Oopsmp2

We develop path-planning algorithms that allow mobile robots to move autonomously while avoiding obstacles. The path-planning algorithms we develop are also suitable for calculating collision-free trajectories for articulated robot arms.

We also develop task-planning algorithms that are useful in many applications to compute an optimal sequence of actions or an optimal set of reaction rules for achieving a given objective. In mobile robotics, these algorithms are used to automate the robot decision making process by enabling robots to determine the sequence of actions that is necessary to achieve a given goal in a given situation. For instance, a robot asked to repair a given device would use a task-planner to decompose the repair task into elementary subtasks, each accomplished by a sequence of actions.

In many applications, the execution of plans can fail due to uncertainty in sensor readings, intrinsic limitations in actuators, unpredicted events in the environment, or inaccurate models of action and environment used in the planning process. For instance, a robot may be using outdated maps and its sensors or actuators may fail. We investigate and develop plan execution and monitoring algorithms to detect failures and recover from them.

Plan

Planning is not just about automating decision making processes. It can also be about supporting users in complex decision making processes where the decisions are about determining what actions to do, when, and with what resources given some constraints and possibly some optimization criteria. In such a decision support setting, a planning algorithm is used by an advisory system to recommend actions to users and/or to check that users are performing tasks correctly. We investigate such mixed-initiative approaches to planning and their applications to user decision support.

We also investigate plan recognition algorithms, which are algorithms for recognizing the plan, goal or intent of an agent by observing its actions or the effects of its actions. Being able to recognize plans, intent and activities is a key aspect of human intelligence and plays a role in many applications, ranging from threat evaluations to the control of teams of collaborating robots.

Starcraft

We are currently interested in developing a testbed for integrated decision making and plan recognition algorithms in adversarial domains such as RTS games. We have implemented an intelligent agent which participated in the AIIDE 2011 StarCraft AI Competition. For more information, please consult the SPAR project page.

Is planning all about robots?

Roman Tutor

So far most of our planning research has been applied to robotics, but robots are by no means the only application domains. In 2008, we began a project for applying plan recognition to evaluate threats in naval warfare.

Elsewhere, many applications deal with logistic planning, particularly space mission planning. In the military, there are planning problems at a large spectrum going from missile defence problems to tactical planning and logistic planning. Planning has not yet made its way to the video game industry (except to a small extent path-planning), but it seems there is a good potential there.

We remain open to opportunities for collaboration with the industry on applying planning and plan recognition concepts and techniques.

Want to know more?

For inquiries, contact Froduald Kabanza. You are also encouraged to browse through the web pages of the team members.