Files in this item



application/pdf9624406.pdf (11MB)Restricted to U of Illinois
(no description provided)PDF


Title:A game-theoretic framework for robot motion planning
Author(s):LaValle, Steven Michael
Doctoral Committee Chair(s):Hutchinson, Seth A.
Department / Program:Engineering, Electronics and Electrical
Computer Science
Discipline:Engineering, Electronics and Electrical
Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
Abstract:The primary contribution of this dissertation is the presentation of a dynamic game-theoretic framework that is used as an analytical tool and unifying perspective for a wide class of problems in robot motion planning. The framework provides a precise mathematical characterization that can incorporate any of the essential features of decision theory, stochastic optimal control, and traditional multiplayer games. The determination of strategies that optimize some precise performance functionals is central to these subjects, and is of fundamental value for many types of motion planning problems.
The basic motion planning problem is to compute a collision-free trajectory for the robot, given perfect sensing, an exact representation of the environment, and completely predictable execution. The best-known algorithms have exponential complexity, and most extensions to the basic problem are provably intractable. The techniques in this dissertation characterize several extensions to the basic motion planning problem, and lead to computational techniques that provide practical, approximate solutions. A general perspective on motion planning is also provided by relating the similarities between various extensions to the basic problem within a common mathematical framework.
Modeling, analysis, algorithms, and computed examples are presented for each of three problems: (1) motion planning under uncertainty in sensing and control; (2) motion planning under environment uncertainties; and (3) multiple-robot motion planning. Traditional approaches to the first problem are often based on a methodology known as preimage planning, which involves worst-case analysis. In this context, a general method for determining feedback strategies is developed by blending ideas from stochastic optimal control and dynamic game theory with traditional preimage planning concepts. This generalizes classical preimages to performance preimages and preimage plans to motion strategies with information feedback. For the second problem, robot strategies are analyzed and determined for situations in which the environment of the robot is changing, but not completely predictable. Several new applications are identified for this context. The changing environment is treated in a flexible manner by combining traditional configuration space concepts with stochastic optimal control concepts. For the third problem, dynamic game-theoretic and multiobjective optimization concepts are applied to motion planning for multiple robots. This allows the synthesis of motion plans that simultaneously optimize an independent performance criterion for each robot. Several versions of the formulation are considered: fixed-path coordination, coordination on independent configuration-space roadmaps, and centralized planning.
Issue Date:1995
Rights Information:Copyright 1995 LaValle, Steven Michael
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9624406
OCLC Identifier:(UMI)AAI9624406

This item appears in the following Collection(s)

Item Statistics