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

## ANY-ANGLE PATH PLANNING

by

Alex Nash

A Dissertation Presented to the

## FACULTY OF THE USC GRADUATE SCHOOL

## UNIVERSITY OF SOUTHERN CALIFORNIA

In Partial Fulﬁllment 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 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.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, 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