WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 43 |

«ANY-ANGLE PATH PLANNING by Alex Nash A Dissertation Presented to the FACULTY OF THE USC GRADUATE SCHOOL UNIVERSITY OF SOUTHERN CALIFORNIA In Partial ...»

-- [ Page 1 ] --

ANY-ANGLE PATH PLANNING

by

Alex Nash

A Dissertation Presented to the

FACULTY OF THE USC GRADUATE SCHOOL

UNIVERSITY OF SOUTHERN CALIFORNIA

In Partial Fulfillment of the

Requirements for the Degree

DOCTOR OF PHILOSOPHY

(COMPUTER SCIENCE)

August 2012

Copyright 2012 Alex Nash Table of Contents List of Tables vii List of Figures ix

Abstract

xii Chapter 1: Introduction 1

1.1 Path Planning.................................... 2 1.1.1 The Generate-Graph Problem....................... 3 1.1.2 Notation and Definitions.......................... 4 1.1.3 The Find-Path Problem........................... 5

1.2 Hypotheses and Contributions........................... 12 1.2.1 Hypothesis 1................................ 12 1.2.2 Hypothesis 2................................ 12 1.2.2.1 Basic Theta*: Any-Angle Path Planning in Known 2D Environments............................. 14 1.2.2.2 Lazy Theta*: Any-Angle Path Planning in Known 3D Environments............................. 14 1.2.2.3 Incremental Phi*: Any-Angle Path Planning in Unknown 2D Environments.......................... 15

1.3 Dissertation Structure................................ 17 Chapter 2: Path Planning 18

2.1 Navigation...................................... 18

2.2 Path Planning.................................... 19 2.2.1 The Generate-Graph Problem....................... 20 2.2.1.1 Skeletonization Techniques................... 21 2.2.1.2 Cell Decomposition Techniques...

–  –  –

Navigating an agent from a given start coordinate to a given goal coordinate through a continuous environment is one of the most important problems faced by roboticists and video game developers. A key part of navigation is path planning. Path planning is the process of generating a path, defined by a sequence of waypoints, that begins at a given start coordinate, ends a given goal coordinate and avoids obstacles in the continuous environment. Path planning is typically composed of two parts: the generate-graph problem, which is solved by discretizing a continuous environment into a graph and the find-path problem, which is solved by searching this graph for a path from a given start vertex to a given goal vertex. Roboticists and video game developers use many different techniques for solving the generate-graph problem, but the find-path problem is typically solved using a traditional edge-constrained find-path algorithm, such as A*. The reason for this is that traditional edge-constrained find-path algorithms have the following desirable properties: Simplicity Property: They are simple to implement and understand. Efficiency Property: They provide a good tradeoff with respect to the runtime of the search and the length of the resulting path. Generality Property: They can be used to search any Euclidean graph.

However, these desirable properties come with a penalty. Traditional edge-constrained find-path algorithms propagate information along graph edges and constrain paths to be formed by graph edges. This constraint is artificial and causes the paths found by traditional edge-constrained find-path algorithms to be both longer and less realistic looking than the true shortest paths (that is, the shortest paths in the continuous environment). While this fact is well known by roboticists and video game developers two important questions remain: Question 1: How much longer can the paths found by traditional edge-constrained find-path algorithms be than the true shortest paths? Question 2: Can more sophisticated find-path algorithms be developed that find shorter and more realistic looking paths than traditional edge-constrained find-path algorithms, while maintaining the desirable properties of traditional edge-constrained find-path algorithms? This dissertation addresses these two questions and therefore our hypotheses are as follows: Hypothesis 1: Analytical bounds can be introduced which compare the lengths of the paths found by traditional edge-constrained find-path algorithms on certain types of graphs with the lengths of the true shortest paths. Hypothesis 2: A new class of any-angle find-path algorithms, that propagate information along graph edges, without constraining paths to be formed by graph edges, can be used to quickly find paths that are shorter than the paths found by traditional edge-constrained find-path algorithms, while maintaining the Simplicity and Generality Properties of traditional edge-constrained find-path algorithms.

To validate Hypothesis 1, we introduce a comprehensive set of eight new analytical bounds which compare the lengths of the paths found by traditional edge-constrained find-path algorithms on grid graphs constructed from 2D and 3D regular grids with the lengths of the true shortest paths.





xii To validate Hypothesis 2, we introduce a new class of any-angle find-path algorithms that propagate information along graph edges (to achieve a short runtime) without constraining paths to be formed by graph edges (to find any-angle paths). We introduce new members to this class and evaluate each member in one of three types of continuous environments, namely continuous 2D environments in which agents have complete knowledge of the environment (known 2D environments), continuous 3D environments in which agents have complete knowledge of the environment (known 3D environments), and continuous 2D environments in which agents do not have complete knowledge of the environment (unknown 2D environments). For each new any-angle find-path algorithm, we use the Simplicity, Efficiency and Generality Properties as our evaluation criteria. Specifically, we introduce three new any-angle find-path algorithms, namely Basic Theta*, Lazy Theta* and Incremental Phi*. In known 2D environments, Basic Theta* satisfies the Simplicity and Generality Properties, provides a good tradeoff, relative to traditional edge-constrained find-path algorithms, with respect to the runtime of the search and the length of the resulting path and a dominating tradeoff over existing any-angle find-path algorithms with respect to the runtime of the search and the length of the resulting path (Efficiency Property).

Lazy Theta* is a variant of Basic Theta* that is designed for path planning in known 3D environments. In known 3D environments, Lazy Theta* satisfies the Simplicity and Generality Properties, provides a good tradeoff, relative to traditional edge-constrained find-path algorithms, with respect to the runtime of the search and the length of the resulting path and a dominating tradeoff over Basic Theta* with respect to the runtime of the search and the length of the resulting path (Efficiency Property). Incremental Phi* is a variant of Basic Theta* that is designed for path planning in unknown 2D environments. In unknown 2D environments, Incremental Phi* satisfies the Simplicity Property and provides a dominating tradeoff over Basic Theta* with respect to the runtime of the search and the length of the resulting path (Efficiency Property). These contributions demonstrate that any-angle find-path algorithms represent a promising new technique for path planning in robotics and video games.

–  –  –

Introduction Navigating an agent from a given start coordinate to a given goal coordinate through a continuous environment is one of the most important problems faced by roboticists and video game developers. A key part of navigation is path planning. Path planning is the process of generating a path, defined by a sequence of waypoints, that begins at a given start coordinate, ends a given goal coordinate and avoids obstacles in the continuous environment. Path planning is typically composed of two parts: the generate-graph problem, which is solved by discretizing a continuous environment into a graph and the find-path problem, which is solved by searching this graph for a path from a given start vertex to a given goal vertex. Roboticists and video game developers use many different techniques for solving the generate-graph problem, but the find-path problem is typically solved using a traditional edge-constrained find-path algorithm, such as A*. The reason for this is that traditional edge-constrained find-path algorithms have the following desirable properties: Simplicity Property: They are simple to implement and understand. Efficiency Property: They provide a good tradeoff with respect to the runtime of the search and the length of the resulting path. Generality Property: They can be used to search any Euclidean graph.

However, these desirable properties come with a penalty. Traditional edge-constrained find-path algorithms propagate information along graph edges and constrain paths to be formed by graph edges. This constraint is artificial and causes the paths found by traditional edge-constrained find-path algorithms to be both longer and less realistic looking than the true shortest paths (that is, the shortest paths in the continuous environment). While this fact is well known by roboticists and video game developers two important questions remain: Question 1: How much longer can the paths found by traditional edge-constrained find-path algorithms be than the true shortest paths? Question 2: Can more sophisticated find-path algorithms be developed that find shorter and more realistic looking paths than traditional edge-constrained find-path algorithms, while maintaining the desirable properties of traditional edge-constrained find-path algorithms? This dissertation addresses these two questions and therefore our hypotheses are as follows: Hypothesis 1: Analytical bounds can be introduced which compare the lengths of the paths found by traditional edge-constrained find-path algorithms on certain types of graphs with the lengths of the true shortest paths. Hypothesis 2: A new class of any-angle find-path algorithms, that propagate information along graph edges, without constraining paths to be formed by graph edges, can be used to quickly find paths that are shorter than the paths found by traditional edge-constrained find-path algorithms, while maintaining the Simplicity and Generality Properties of traditional edge-constrained find-path algorithms.

To validate Hypothesis 1, we introduce a comprehensive set of eight new analytical bounds which compare the lengths of the paths found by traditional edge-constrained find-path algorithms on grid graphs constructed from 2D and 3D regular grids with the lengths of the true shortest paths.

To validate Hypothesis 2, we introduce a new class of any-angle find-path algorithms that propagate information along graph edges (to achieve a short runtime) without constraining paths to be formed by graph edges (to find any-angle paths). We introduce new members to this class and evaluate each member in one of three types of continuous environments, namely continuous 2D environments in which agents have complete knowledge of the environment (known 2D environments), continuous 3D environments in which agents have complete knowledge of the environment (known 3D environments), and continuous 2D environments in which agents do not have complete knowledge of the environment (unknown 2D environments). Specifically, we introduce Basic Theta*, Lazy Theta* and Incremental Phi* and evaluate them in known 2D environments, known 3D environments and unknown 2D environments, respectively, using the Simplicity, Efficiency and Generality Properties as our evaluation criteria. Basic Theta* and Lazy Theta* satisfy the Simplicity and Generality Properties and provide a good tradeoff with respect to the runtime of the search and the length of the resulting path (Efficiency Property). Incremental Phi* satisfies the Simplicity Property and provides a good tradeoff with respect to the runtime of the search and the length of the resulting path (Efficiency Property).

1.1 Path Planning

Navigating an agent from a given start coordinate to a given goal coordinate through a continuous environment is one of the most important problems faced by roboticists and video game developers (Deloura, 2000; Rabin, 2002, 2004; Latombe, 1991; Murphy, 2000; Choset, Lynch, Hutchinson, Kantor, Burgard, Kavraki, & Thrun, 2005). Agents must be able to navigate between coordinates in a realistic manner without getting lost, getting stuck or bumping into obstacles.

When navigating an agent from a given start coordinate to a given goal coordinate one must address both path planning, which is the process of generating a path, defined by a sequence of waypoints, that begins at a given start coordinate, ends a given goal coordinate and avoids obstacles in the continuous environment and movement, which is the process of taking a path and following it in a such a manner that takes into account the kinematic actions and dynamic constraints of the agent. Addressing path planning and movement simultaneously is extremely difficult (Latombe, 1991; Reif, 1979; Canny, 1988) and thus it is common to treat path planning and movement as two separate problems (Patel, 2000; Ferguson, 2006). We are interested in path planning. Path planning is important because it allows an agent to plan ahead rather than just reacting to the environment. When an agent reacts to an environment (that is, movement) without planning ahead (that is, path planning) it is less likely to follow a short and realistic looking path.

Path planning is typically composed of two parts: the generate-graph problem, which is solved by discretizing a continuous environment into a graph and the find-path problem, which is solved by searching this graph for a path from a given start vertex to a given goal vertex (Wooden, 2006; Murphy, 2000).

A Start A Start Start

–  –  –

Figure 1.2: 8-Neighbor Nav Graph Constructed from a Continuous Environment Discretized into a NavMesh (adapted from (Patel, 2000)) 1.

1.1 The Generate-Graph Problem

–  –  –



Pages:   || 2 | 3 | 4 | 5 |   ...   | 43 |


Similar works:

«Model Studies of Proposed Intermediates in Homogeneous Gold(I) Catalysis by Timothy Justin Brown Department of Chemistry Duke University Date:_Approved: _ Ross A. Widenhoefer, Supervisor _ Katherine J. Franz _ Jiyong Hong _ Qiu Wang Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Chemistry in the Graduate School of Duke University i v ABSTRACT Model Studies of Proposed Intermediates in Homogeneous Gold(I) Catalysis by...»

«RAILROAD BARON, FIRE-EATER, AND THE “ALIEN JEW”: THE LIFE AND MEMORY OF DAVID LEVY YULEE By MAURICE I. WISEMAN A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2011 1 © 2011 Maurice I. Wiseman 2 To my friends and family 3 ACKNOWLEDGMENTS I thank my committee, and especially my dissertation advisor Jack Davis, for their valued suggestions and insights that...»

«Introduction The practice of asceticism—religiously or philosophically motivated selfdenial1—had been a part of Christian spirituality from the time of the apostles: it was a feature that Christianity shared with many other GrecoRoman philosophies and religions.2 At the end of the third century AD, however, a new ascetic movement appeared—Christian monasticism.3 Christians began to renounce the traditional expectations of society: men cast off their tax burdens; women refused the path of...»

«HIGH-RESOLUTION THREE-DIMENSIONAL PLUME MODELING WITH EULERIAN ATMOSPHERIC CHEMISTRY AND TRANSPORT MODELS A Dissertation Presented to The Academic Faculty by Fernando García Menéndez In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the School of Civil and Environmental Engineering Georgia Institute of Technology December, 2013 COPYRIGHT 2013 BY FERNANDO GARCIA MENENDEZ HIGH-RESOLUTION THREE-DIMENSIONAL PLUME MODELING WITH EULERIAN ATMOSPHERIC CHEMISTRY AND...»

«THE FAMILY OF GOD: UNIVERSALISM AND DOMESTICITY IN ALICE CARY’S FICTION A Dissertation by JANE M. GALLIHER Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY August 2009 Major Subject: English THE FAMILY OF GOD: UNIVERSALISM AND DOMESTICITY IN ALICE CARY’S FICTION A Dissertation by JANE M.GALLIHER Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the...»

«IRON FILE SYSTEMS by Vijayan Prabhakaran B.E. Computer Sciences (Regional Engineering College, Trichy, India) 2000 M.S. Computer Sciences (University of Wisconsin-Madison) 2003 A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Sciences University of Wisconsin-Madison Committee in charge: Andrea C. Arpaci-Dusseau (Co-chair) Remzi H. Arpaci-Dusseau (Co-chair) David J. DeWitt Mary K. Vernon Mikko H. Lipasti ii iv v Abstract IRON...»

«Curriculum Vitae of Roger Strand Roger Strand is a Norwegian citizen, born in Kristiansund (Norway) 20 May 1968. He is a trained natural scientist (cand. scient. (biochemistry, 1992) and dr. scient., (biochemistry, 1998), both degrees from the University of Bergen, Norway) with additional undergraduate studies in philosophy and Classical Latin. Since 1993, he has been affiliated with the Centre for the Study of the Sciences and the Humanities (Senter for vitenskapsteori, SVT), University of...»

«Descartes’ Meditations on First Philosophy Meditation 1: Concerning Those Things That Can Be Called Into Doubt (27-30.1) Descartes wants to establish a firm foundation for his beliefs, having noted that many of the beliefs he has held in the past have turned out to be false. METHOD OF DOUBT: “reason now persuades me that I should withhold my assent no less carefully from opinions that are not completely certain and indubitable than I would from those that are patently false.” Sceptical...»

«19 Natascia Leonardi* ‘Ontology’ and Terminological Frameworks: an Overview of Issues and Term(s)1 Abstract This paper addresses the question of the protean nature of ‘ontology’, with special attention paid to its use within the domain of terminology theories and applications. This term is widely used nowadays within various disciplines for designating different types of organising relational frameworks. Yet, its designations remain unvaried and, in this way, it causes ambiguity. The...»

«UNIVERSITY OF CALIFORNIA Santa Barbara Analysis of Geographically Embedded Networks A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Geography by John Alan Glennon Committee in charge: Professor Michael Goodchild, Chair Professor Richard Church Professor Keith Clarke Professor Shih-Lung Shaw March 2013 The dissertation of John Alan Glennon is approved. Richard Church Keith Clarke Shih-Lung Shaw Michael Goodchild, Committee Chair...»

«ABSTRACT Title of Document: THE EFFECTS OF BUILDING INFORMATION MODELING ON CONSTRUCTION SITE PRODUCTIVITY Douglas E. Chelson, Doctor of Philosophy, 2010 Directed By: Professor Miroslaw J. Skibniewski, Ph.D., A. James Clark Chair Civil & Environmental Engineering Construction experiences low productivity compared to other industries, largely attributed to poor planning and communication. Building Information Modeling (BIM) is a process that is used to resolve these problems by simulating...»

«TEMPLATE BASED ASYNCHRONOUS DESIGN By Recep Ozgur Ozdag A Dissertation Presented to the FACULTY OF THE GRADUATE SCHOOL UNIVERSITY OF SOUTHERN CALIFORNIA In Partial Fulfillment of the Requirements for the Degree DOCTOR OF PHILOSOPHY (ELECTRICAL ENGINEERING) November 2003 Copyright 2003 Recep Ozgur Ozdag Contents List of Tables v List of Figures vi Abstract ix 1. Introduction 1.1 Asynchronous Circuit Design Flow 1.2 Expected Contributions of the Thesis 1.3 Thesis Organization 2. Background 2.1...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.