Article
files/mazewalls

Problem Representation for Planning Algorithms 101

Gabriel Ware on January 10, 2008

This article was contributed by Gabriel Ware, who works at Pam Development (2K Paris) as a PS3 programmer.

Planners are among the most popular algorithms used in the video game industry, as they solve a broad range of problems ranging from path-finding to action planning. Even though they have their pitfalls, developers regularly use a variety algorithms belonging to the planning family.

When applying a planner in practice, it’s important to get the representation right. Not only can it save you a huge amount of work, but it’ll also help choose the right tool to solve the problem efficiently. Chances are, it’ll also improve the way the team communicates about the design too!

This first part of this article provides a quick overview of the planning problem, giving you the opportunity to learn some of the definitions behind planners. Then, thanks to an example of planning a path inside a navigation mesh, you’ll get an idea of how to apply these techniques to game development.

What’s the Problem?

Planners solve any problem that can be expressed as a succession of steps from a starting point to an end point, using a domain definition and a temporal notion. The domain is generally a set a variables that can take several values to express different states. Defining a plan as a succession of states implies a temporal notion: each point of plan, also called states of the domain, needs to be reached one after another.

In order to go from a state to another, a planner requires the concept of actions. When applied to a state object, an action with side-effects results in the creation of another state. In others words, actions make transitions between states possible.

A planning problem will therefore be expressed as:

  • A domain on which we will operate

  • Objects that will help us describe states

  • A set of Actions modifying Objects, thus creating transitions between states

  • An initial state

  • A goal

Taking the path-finding problem as an example, it can be expressed using the following points:

  • The map as a domain

  • Position objects (the possible states)

  • Moves (as actions)

  • A starting position s

  • a goal position g

The goal is to find a “path” from s to g, i.e. plan the different moves our agents will have to make in order to travel from s to g.

Planning Problem Domain


Figure 1: An example problem domain expressed as a graph. The nodes represent different states that different objects; the arrows represent actions.

What’s the Plan?

90% of the job when applying planning algorithms is to carefully describe the domain, since it is from the domain that each state is extracted.

A domain is usually defined by two things:

  1. Predicates, which will be used to describe states. You can think of them as functions to check states’ attributes (also known as conditions).

  2. Actions and effects, which will be used to travel through states.

Simply put, the solution the planner is searching for is a succession of actions, each having its own effects that are driving the character from the starting point to the end point.

Silence… and Action!

Since the plan is a set of consecutive actions to be carried out, it seems normal to pay close attention to the definition of actions in planning. Continuing the example of path planning, here’s what the domain would look like:

Domain Name: Map 1
Predicates: Agent, NavPoly0, NavPoly1, ..., NavPolyN
Actions: Move1, Move2

And the problem is expressed as:

Start State: Agent in NavPoly0 = true
Goal State: Agent in NavPoly9 = true

Obviously, this description is missing something vital for solve the problem: a way to represent how NavPolygons are connected, from the agent point of view.

That’s where the actions come into play. Actions are a way to express transitions between states. In this example, actions modify the current position by moving the agent from a NavPoly to another.

For the programmers among you, an action can be viewed as a function taking parameters, and having effects on the current state of the domain being worked on. Also it’s usually necessary to have preconditions to actions, to ensure that they are correctly used by the planners.

To summarize, an action is made of:

  • Parameters

  • Effects

  • Preconditions (made of domain predicates)

For example, actions useful for path finding would be:

Action In(Agent, NavPoly)
    - Effect return true if agent is in NavPoly
Action Adjacent(NavPolyCurrent, NavPolyNext)
    - Effect return true if NavPolyCurrent is connected to NavPolyNext
Action Move(Agent, NavPolyCurrent, NavPolyNext)
    - Precondition Adjacent(NavPolyCurrent, NavPolyNext) = True
    - Effect In(Agent, NavPolyCurrent) = False
    - Effect In(Agnet, NavPolyNext) = True

Algorithms

Actions let you create a graph of states where you can search for a valid answer, which is the goal state. The concept of planning is composed up of two stages:

  • Sampling the domain, which means that using various methods you get some states out of your domain definition (either by chaining actions one after another, or by applying random, when applicable, to your domain objects).

  • Searching inside a graph made of samples, where transitions between states are actions. A plan is a path inside the graph linking your start node to the goal node.

As such, most graph algorithms are helpful for planning task.

Planning Path-Finding

Photo 2: The most complex mazes can be solved by planners.

Also, the fact that you are sampling a domain matters a lot. In some cases you’ll be able to construct a full graph, use informed search, and some times the domain is just too vast to sample each state and use naive algorithm. The complexity of your domain will mostly drive the choice of the algorithm.

Sources

An Introduction to Algorithms

Concerning the search a lot of information can be taken from graph theory, a good start would be Artificial Intelligence a Modern Approach by Stuart Russell and Peter Norvig. Also see An Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.

Concerning planning theory, a very good online resource is the book on Planning Algorithms available online. For those who wants to go deeper, and want to see what a planning specific language would look like, look into the Planning Domain Definition Language (a.k.a. PDDL).

Summary

This post has presented the building blocks of planning: what to describe and analyze when faced with a planning problem, how to represent the domain formally, and what algorithms to apply.

How do you describe your planning problems and what techniques do you use to solve them?

Discussion 1 Comments

gware on January 11th, 2008

I'd like to thank Alex for all his help with this article. He help me a lot with the edition and gave me great advices. Thanks Alex !

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!