MEAM Ph.D. Thesis Defense: “Exploiting Flows for Orienteering and Planning Problems”

Task and path planning algorithms for robots in the presence of flows confront a fundamental dichotomy between the continuous and the discrete: task planning algorithms discretize the world and their goals, whereas flows are continuous in nature. This contrast is exemplified in many robotic applications where environmental forces impact navigation and exploiting those flows is critical for the quality of results. In this work, we address methods for connecting continuous models of the environment with planning methods for robot motion in high-level task planning with low-level path planning.
First, we examine a problem that focuses on the high level problem of task planning, but abstracts away the environment and assumes that the low-level path planning is solved independently. This helps simplify the problem, but neglects to include environmental information which is often fundamentally linked to the vehicle motion. Next, we address this limitation by exploring path planning algorithms in environments that are represented by an external flow field, such as static and time-varying ocean currents. While we cannot control the external currents, our planning method considers the trade-offs between energy efficiency, reward collection, and time budget based on the interplay of the chosen routes, paths, and environment. Lastly, we expand our analysis to the joint problem of both designing the environmental flows and path planning within the designed flow fields. We explore this problem in the context of controlling magnetically driven milli-robots. We show how we can circumvent the need to solve the inverse dynamics problem with complete knowledge of the global field by extracting key features from the generated fields. These features enable us to take a topological approach to discretize the search space and design advantageous paths.