Catalogue of Artificial Intelligence Techniques
Aliases: Variational Dynamic Programming
Keywords: dynamic programming, path, planning, robot manipulation
Author(s): Carmen Istrate
Dynamic programming as a technique was developed in the 1950s by Richard Bellman, as a method of making decisions over time or stages. It has found many applications since, and is by no means restricted to decision making over time. The principle of DP is to divide a problem into subproblems, which are in turn divided into further subproblems. The deepest level subproblems are first evaluated, followed by the ones immediately depending on them, and so on, up to the original problem. This is a bottom-up approach. The efficiency of DP relies on the fact that subproblems are characterised by their state, so subproblems with the same state will have identical optimal solutions, and are therefore equivalent as far as the optimisation is concerned.
An important application in the field of Artificial Intelligence has been the use of DP methods to solve robot path planning problems. This avoids the problem specific heuristics, like potential functions, which have been used to model fields that would attract the robot towards its target, and therefore makes it possible to solve higher dimension path finding problems. The generality of this method makes it applicable to a wide range of manipulation task planning problems, which would otherwise be difficult to model with problem specific heuristics.
The method consists in iteratively improving an initial path (possibly colliding with obstacles). At each iteration, the program performs a search over a k-dimensional submanifold of the n-dimensional configuration space containing the current path. In practice, k is chosen as 2,3 or 4, for performance issues. The k-dimensional manifold is an arbitrarily chosen ruled surface, containing the current path. This surface is quantised into a k-dimensional grid of configurations, and is then searched with Dijkstra's algorithm, which has an additive cost function proportional to the number of configurations colliding with obstacles. Therefore it is certain that fewer points will collide with obstacles in the new path. The search is repeated until a clear path is obtained.
- Jerome Barraquand and Pierre Ferbach, Path planning through variational dynamic programming PRL-RR-33 (Paris Research Laboratory) (1993), 1,2.