Thesis Defense - Otte

Robust autonomous robotic systems must use complete path planning algorithms when less expensive methods fail, but finding complete solutions to the multi-robot path planning problem is computationally complex. 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 "Gossiping Any-Time search progress between robots in an ad-hoc distributed computer enables centralized multi-robot path-planning that maximizes completeness with respect to the available computational resource and communication quality."

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.