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

## UNIVERSITY OF SOUTHERN CALIFORNIA

In Partial Fulﬁllment of the

Requirements for the Degree

## DOCTOR OF PHILOSOPHY

(COMPUTER SCIENCE)

August 2012

Abstract

xii Chapter 1: Introduction 1

1.1 Path Planning.................................... 2 1.1.1 The Generate-Graph Problem....................... 3 1.1.2 Notation and Deﬁnitions.......................... 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.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, deﬁned 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 ﬁnd-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 ﬁnd-path problem is typically solved using a traditional edge-constrained ﬁnd-path algorithm, such as A*. The reason for this is that traditional edge-constrained ﬁnd-path algorithms have the following desirable properties: Simplicity Property: They are simple to implement and understand. Efﬁciency 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 ﬁnd-path algorithms propagate information along graph edges and constrain paths to be formed by graph edges. This constraint is artiﬁcial and causes the paths found by traditional edge-constrained ﬁnd-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 ﬁnd-path algorithms be than the true shortest paths? Question 2: Can more sophisticated ﬁnd-path algorithms be developed that ﬁnd shorter and more realistic looking paths than traditional edge-constrained ﬁnd-path algorithms, while maintaining the desirable properties of traditional edge-constrained ﬁnd-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 ﬁnd-path algorithms on certain types of graphs with the lengths of the true shortest paths. Hypothesis 2: A new class of any-angle ﬁnd-path algorithms, that propagate information along graph edges, without constraining paths to be formed by graph edges, can be used to quickly ﬁnd paths that are shorter than the paths found by traditional edge-constrained ﬁnd-path algorithms, while maintaining the Simplicity and Generality Properties of traditional edge-constrained ﬁnd-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 ﬁnd-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 ﬁnd-path algorithms that propagate information along graph edges (to achieve a short runtime) without constraining paths to be formed by graph edges (to ﬁnd 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 ﬁnd-path algorithm, we use the Simplicity, Efﬁciency and Generality Properties as our evaluation criteria. Speciﬁcally, we introduce three new any-angle ﬁnd-path algorithms, namely Basic Theta*, Lazy Theta* and Incremental Phi*. In known 2D environments, Basic Theta* satisﬁes the Simplicity and Generality Properties, provides a good tradeoff, relative to traditional edge-constrained ﬁnd-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 ﬁnd-path algorithms with respect to the runtime of the search and the length of the resulting path (Efﬁciency 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* satisﬁes the Simplicity and Generality Properties, provides a good tradeoff, relative to traditional edge-constrained ﬁnd-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 (Efﬁciency 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* satisﬁes 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 (Efﬁciency Property). These contributions demonstrate that any-angle ﬁnd-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, deﬁned 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 ﬁnd-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 ﬁnd-path problem is typically solved using a traditional edge-constrained ﬁnd-path algorithm, such as A*. The reason for this is that traditional edge-constrained ﬁnd-path algorithms have the following desirable properties: Simplicity Property: They are simple to implement and understand. Efﬁciency 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 ﬁnd-path algorithms propagate information along graph edges and constrain paths to be formed by graph edges. This constraint is artiﬁcial and causes the paths found by traditional edge-constrained ﬁnd-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 ﬁnd-path algorithms be than the true shortest paths? Question 2: Can more sophisticated ﬁnd-path algorithms be developed that ﬁnd shorter and more realistic looking paths than traditional edge-constrained ﬁnd-path algorithms, while maintaining the desirable properties of traditional edge-constrained ﬁnd-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 ﬁnd-path algorithms on certain types of graphs with the lengths of the true shortest paths. Hypothesis 2: A new class of any-angle ﬁnd-path algorithms, that propagate information along graph edges, without constraining paths to be formed by graph edges, can be used to quickly ﬁnd paths that are shorter than the paths found by traditional edge-constrained ﬁnd-path algorithms, while maintaining the Simplicity and Generality Properties of traditional edge-constrained ﬁnd-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 ﬁnd-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 ﬁnd-path algorithms that propagate information along graph edges (to achieve a short runtime) without constraining paths to be formed by graph edges (to ﬁnd 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). Speciﬁcally, 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, Efﬁciency 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 (Efﬁciency Property). Incremental Phi* satisﬁes the Simplicity Property and provides a good tradeoff with respect to the runtime of the search and the length of the resulting path (Efﬁciency 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, deﬁned 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 difﬁcult (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 ﬁnd-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 fulﬁllment 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.