A game-theoretic framework for robot motion planning
LaValle, Steven Michael
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/23609
Description
Title
A game-theoretic framework for robot motion planning
Author(s)
LaValle, Steven Michael
Issue Date
1995
Doctoral Committee Chair(s)
Hutchinson, Seth A.
Department of Study
Engineering, Electronics and Electrical
Computer Science
Discipline
Engineering, Electronics and Electrical
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
