Date of Award

Spring 1-1-2011

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Nikolaus Correll

Second Advisor

Michael Mozer

Third Advisor

Richard Han

Abstract

Robust autonomous robotic systems must use complete or probabilistically complete path planning algorithms when less expensive methods fail (where completeness is the algorithmic property of being able to find a solution to a problem when one exists). However, these methods are sometimes so computationally complex that a solution cannot be found within a reasonable amount of time. Communication between robots tends to increase completeness and reduce computational complexity; however, communication quality is environmentally dependent and often beyond control of the user or system. Previous approaches to the multi-robot path planning problem have each been tailored to a single point within the completeness vs. computational vs. communication state space, and are often ill-equipped to solve problems outside their design envelope. In contrast, I believe that truly robust multi-robot navigation can only be achieved by algorithms that automatically tune their performance within this state space to maximize performance vs. each problem the system faces. My personal bias is to maximize algorithmic completeness while respecting the computational resource and communication quality that is currently available. In order to be useful, the resulting solutions must be calculated within a reasonable amount of time. I also believe that it makes sense to divide the computational effort of finding multi-robot path planning solutions among all robots that the solution will benefit. This can be accomplished by recasting a networked team of robots as an ad-hoc distributed computer---allowing the team's computational resources to be pooled increases the complexity of problems that can be solved within a particular amount of time. However, distributed computation in an ad-hoc framework must respect the fact that communication between computational nodes (i.e., robots) is usually unreliable. I propose the thesis “Sharing Any-Time search progress over an ad-hoc distributed computer that is created from a dynamic team of robots enables probabilistically complete, centralized, multi-robot path-planning across a broad class of instances with varied complexity, communication quality, and computational resources.” The work presented in this dissertation in support of my thesis can be divided into three related areas of focus. (1) I propose a new distributed planning concept called Coupled Forests Of Random Engrafting Search Trees (C-FOREST), and demonstrate that it has parallelization efficiency greater than 1 for many problems. (2) I propose using a robotic team as an ad-hoc distributed computing cluster, and demonstrate that when C-FOREST is run on this type of architecture it is able to exploit perfect communication when it exists, but also has graceful performance declines as communication quality deteriorates. I coin the term “Any-Com” to describe algorithms with the latter property. (3) I propose a dynamic team version of Any-Com C-FOREST that allows multiple robotic teams to form and then re-form as robots move about the environment. Each team acts as an ad-hoc distributed computer to solve its composite robots' communal path planning problem. Limiting teams to include only conflicting robots improves algorithmic performance because it significantly reduces the computational complexity of the problem that each team must solve. Replanning through only the subset of the configuration space in which conflicts occurs has similar computational benefits.

Share

COinS