[an error occurred while processing this directive]

Minimum Link Paths for tactical game scenarios in a constraint-based algorithm

Nicolas Galoppo von Borries, COMP290-58 project proposal, Fall 2003

Update: proposal slides available.

Introduction

Classically, there are three major approaches for solving motion planning problems: road maps, cell decomposition and potential field methods. Potential field methods are able to deal with arbitrary constraint requirements, but may get stuck in local minima of the navigation potential function. On the other hand, complete road maps are hard to compute in general.

Recently, Garber and Lin [1] proposed an algorithm that formulates the planning problem as a simulation of a constrained dynamical system, guided by Voronoi Diagrams. This approach gracefully combines road maps and potential field methods, using the road map as a global goal. The idea is to overcome the local minima problem by using a road map method for navigation, while maintaining the constraint generalization that potential field methods offer. The general characteristic of the above method applies well to multiple tactical game agents, as they are typically driven by so-called behavioral constraints. Some of these constraints include the need to stay in group, follow a leader, cover an area, keep possession of captured material and maintain line-of-sight for communication purposes.


Figure 1: A Voronoi-based path (red) compared to a MLP (green)

While Voronoi diagrams yield paths that avoid the objects in the scene optimally, this does not always apply well to tactical game scenarios. Here, mobile agents want to stay close to the objects, taking cover from threats in the environment.

Approach and motivation

Minimum-link paths (MLP) minimize the number of straight-line segments between starting point and goal. As opposed to Voronoi diagrams, minimum-length paths typically pass by the corners and along borders of the objects in the scene. The idea is to replace the Voronoi diagram navigational component in Garber and Lin's algorithm by an MLP approach, hopefully forcing the automated tactical agents to stay covered behind the objects and spend less time 'in the open', although it is not clear if the minimization of the number of turns will yield appropriate paths.

Minimum-link paths are computed for a single query only, whereas Voronoi diagrams give a complete representation of the free space in one computation. Therefore, Voronoi diagrams are more suited to static environments. Nevertheless, game scenarios often contain moving objects, such as cars, trucks, moving platforms and sliding doors, that could also be used by the tactical agents to hide behind. This requires a new planning query every time the environment changes. Luckily, Hershberger and Snoeyink [2] describe a simple linear-time algorithm for computing minimum-link paths in simple polygons for a given homotopy class. Therefore, under small object transformations, the previous MLP result can be reused for an efficient update of the path. The algorithm also provides the ability to restrict the paths to c given directions.

In summary, combining minimum-link paths with constraint-based motion planning will hopefully show the following properties, beneficial to tactical agent scenarios:

Goals

This project will focus on the following goals: Other interesting possibilities include:

References

     [1] Constraint-Based Motion Planning using Voronoi Diagrams. Maxim Garber and Ming C. Lin, Proc. Fifth International Workshop on Algorithmic Foundations of Robotics (WAFR), 2002

     [2] Computing minimum length paths of a given homotopy class. Hershberger, J. and Snoeyink, J., Computational Geometry: Theory and Applications 4 (1994), 63--97.

     [3] SIGGRAPH 2002 Course: Interactive Geometric Computations Using Graphics Hardware. Dinesh Manocha, et al. [schedule] [course notes]
[an error occurred while processing this directive]