{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23609"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23609","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A game-theoretic framework for robot motion planning","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.","abstract_html":"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.","abstract_has_math":false,"creators":["LaValle, Steven Michael"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Engineering, Electronics and Electrical","degree_department":null,"school":null,"contributors":["Hutchinson, Seth A."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:20:30Z","date_published":"2011-05-07T14:20:30Z","updated_at":"2026-07-22T22:25:22Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1995 LaValle, Steven Michael"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624406","(UMI)AAI9624406"],"render_values":[{"text":"AAI9624406","href":null,"code":true},{"text":"(UMI)AAI9624406","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23609","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hutchinson, Seth A."]},{"key":"dc:creator","label":"Author","values":["LaValle, Steven Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:20:30Z","10000-01-01","1995"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering, Electronics and Electrical","Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 LaValle, Steven Michael"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624406","(UMI)AAI9624406","http://hdl.handle.net/2142/23609"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T14:20:30Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624406.pdf: 11371905 bytes, checksum: 4730e28b712398f83f1bf8e90ccf075d (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:05:38Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:27-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["A game-theoretic framework for robot motion planning"]}]}],"canonical_facts":{"dc:contributor":["Hutchinson, Seth A."],"dc:creator":["LaValle, Steven Michael"],"dc:date":["2011-05-07T14:20:30Z","10000-01-01","1995"],"dc:description":["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.","Made available in DSpace on 2011-05-07T14:20:30Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624406.pdf: 11371905 bytes, checksum: 4730e28b712398f83f1bf8e90ccf075d (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:05:38Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:27-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9624406","(UMI)AAI9624406","http://hdl.handle.net/2142/23609"],"dc:language":["eng"],"dc:rights":["Copyright 1995 LaValle, Steven Michael"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["A game-theoretic framework for robot motion planning"],"dc:type":["text"],"thesis:degree_discipline":["Engineering, Electronics and Electrical","Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:22Z"}