Path-Planning from Start to Finish
By ai-depot | June 30, 2002
The fifth issue of a multi-part tutorial covering all the aspects of path planning. This issue discusses single-pair shortest-path problems, with the different kinds of searches that can solve them. A* (star) is then explained as a heuristic approach; with pseudo-code and optimisation ideas.
Written by Alex J. Champandard.
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:
- Path planning is the art of deciding which route to take, based on and expressed in terms of the current internal representation of the terrain.
- Path finding is the execution of this theoretical route, by translating the plan from the internal representation in terms of physical movement in the environment.
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:
- V - Vertices: A set of discreet points in n-space, but this usually corresponds to a 3D world.
- E - Edges: A set of connections between the vertices, which can be either directed or not.
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:
- n = |V| - The number of vertices in the graph.
- m = |E| - The number of edges in the graph.
- c - The maximum absolute length of an edge.
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:
- Dense/Sparse graphs - The difference is in the number of edges, respectively O(n^2) and O(n).
- Irregular/Homogenous edge costs - Are all path lengths are within the same range all round?
- Localised/Random connections - Do we have any kind of logical structure inside the graph?
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:
- Human like behaviour - Often, when a perfect path is chosen, it is voluntarily falsified to provide a more realistic behaviour. This can be done by adding noise to the path-costs, selecting the destination in a fuzzy fashion, or randomly picking an intermediary target waypoint.
- Imperfect internal state - For embedded agents, information does not flow freely. They are limited by what they perceive, and therefore, their internal representation of the world may be false. In such a premise, what seems like a perfect decision may be just as detrimental as a slightly imperfect one.
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:
- Single Pair - These algorithms take a specific source and destination. Only one path is required in response, and this is usually assumed to be the most optimal.
- Single Source - In this type algorithm, the path from one node to all the others is required.
- All Pairs - The algorithm must return the shortest paths from every waypoint to all the others. This is naturally the most computationally expensive.
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:
- Complete path generation - The complete route to be taken is created as a sequence of moves from the initial position.
- Next move selection - At each step, the algorithm must decide which way to move next. An efficient dynamic implementation is obviously required here, if the overhead is to be minimised.
- Forward planning - The properties of the path can be taken into account by a deliberative thinking module, responsible for making founded decisions. For example, path lengths can be used to estimate travel-time, which influences the agent’s decision to move to a particular location.
- Anticipation - As an extension to the previous bullet-point, the path-planning algorithm can be used to take into account other agents’ behaviours.
Tags: none
Category: tutorial |
