Problem Description

As we develop virtual environments increasingly interesting, larger and more complex, the ability of agents to consciously find their way around the terrain plays a more important role in their behaviour. This tutorial takes on the role of a generic introduction to the subject, attempting to clear up many confusions and misinterpretations. This will be achieved by providing a general definition of the task at hand, which will be formalised further thanks to the cunning use of mathematics. Once these abstract concepts have been presented, a solid base for judging specific algorithms and implementations will have been constructed.

In practice, we'll first start by looking at single-source shortest path algorithms, including Dijkstra's approach -- a milestone for single source shortest path problems. Then, the Bellman-Ford-Moore algorithm will be described, bringing the benefit and disadvantage of negative path-lengths to the mix. A* seems to be a classic for game AI, so that will be discussed next -- and the parallels with D* will be made. Finally, the Floyd-Warshall "all the paths" algorithm will be analysed. Once all the theory has been covered, a quick comparison will be made, and implementation details will be discussed.

All this will hopefully disassociate in your mind any particular implementation to the problem, and open your eyes on the path-planning issue. You'll notice that there's much more out there than the A* algorithm. Then by mixing and matching these algorithms, you should be able to find an implementation that suits your needs. There's much to be done, so lets get cracking.

Definitions

For agents, premeditated movement can usually be split into two parts; the decision phase and the execution phase. Though this separation is key for many robot-based approaches, it is seldom made explicit in existing game AI. The simplistic nature of current environments is the major cause for this. Indeed, once planned, the moves are usually assumed to be possible and the a-priory plan is rarely reconsidered.

We propose the following definitions:

Despite some applications requiring a blend the two following concepts, the distinction has many advantages including simplicity, a modular implementation, and easy integration of varied research technology.

Also, though these two parts are conceptually different, they interact in many ways that are too important to overlook. Firstly, the planner must naturally let the path finder know of the most recently chosen path. And secondly there needs to be feedback from the finder to the planner so that impossible paths are noted and reconsidered.

Formalisation

Foundations

Any path-planning algorithm must be based on a representation of the terrain. This topic deserves a tutorial of its own, but it suffices to say that somewhat discretised versions of the full environment are stored; some are grid-based, some are looser. The sampling points we are interested in represent empty space -- these are known as vertices or nodes, among many other things. In either case, connectivity between these waypoints needs to be expressed; this is done by paths, arcs or edges (again different names for the same concept).

Conceptually, a graph G is composed of two sets, and can be written as G = (V,E) where:

Together with this structural definition, algorithms also generally need to know about properties of these elements. For example, the length, travel-time or general cost of every edge needs to be known. Mathematically, this is denoted as a function l which maps edges to real numbers:

l: E -> R

This is indirectly used to decide how far a vertex is from another, and how this distance value increases as a path is taken.

Complexity

In computer science, the study of the complexity of algorithms is serious business. This is often expressed in terms of constants involved in the algorithm; and path-planning is no exception. The following quantities are often cited:

For example, one implementation could take O(nm) to find a path. In simple terms, this means it needs a number of constant operations which is around the order of magnitude of n*m.

Evaluation

Though the theoretical analysis usually reveals a lot about the algorithm itself, it often takes practical situations to reveal their pitfalls and benefits. Graphs are often extremely varied in structure, with regards to connectivity, density and size. Specific combinations can stall a particular algorithm, and make it take the worst estimated time. It's a good idea to test your implementation on following:

In most cases, it suffices to test the algorithm on the most common network topology, and keep your fingers crossed! But that wouldn't be very scientific, would it? ;)

Relaxed Attitudes

When dealing with Artificially Intelligent agents, there are many observations and assumptions that can be made. Though at first it can seem an awkward setting to have to handle dynamic conditions, this can be worked to our advantage if we tolerate imperfection. This may sound like a tall order to those of you used to optimal optimisation, but it has many advantages:

By accepting these terms, and discarding the shortest path obsession, we can fall-back to much looser forms of optimisation -- stochastic ones -- which can be used in an incremental fashion. This will be covered later in this column.

Varieties

Path-planning algorithms come in all sizes, shapes and colours -- much like elephants. This is most likely due to their broad applicability, and their history. Indeed, many fields such as networking, graph theory, search and combinatorial optimisation, algorithms and data-structures have contributed to the mix.

Specifically, there are three major types of algorithms. You could derive more types from the trend, but to my knowledge they are rarely used, and these remain the most common:

By sticking to these type of algorithms, but restricting their scope, the desired results can be usually obtained fairly easily. For example efficiently determining all the shortest paths from 10 specific nodes would require restricting the search of the multi-path algorithm.

Application

Before we dig in to more specific details, it seems right to explain how the information will be put to use. As you may expect, there are many reasons for a path planning algorithm, and as many bullet points in the list:

Remember you can visit the Message Store to discuss this tutorial. Comments are always welcome!. There are already replies in the thread, why not join in?