UC Merced

Path planning and path optimization are enduring areas of interest in the fields of computer science and automation. With the increasing presence of autonomous mobile robots in industries such as agriculture, manufacturing, and shipping, it is essential that we develop and improve methods for both planning and optimizing plans for agents in diverse environments. In this thesis I focus on path smoothing and optimization methods with customized properties and their application to optimizing multiple non-intersecting paths, which we also refer to as sets of lanes.

First I propose a new path smoothing method based on the approach of deterministic shortcuts. The presented method addresses limitations of the the popular random shortcuts method, and demonstrates superior results as measured both in terms of path length and smoothness. As common in such methods, the path is represented here as a polygonal line and smoothness quality is measured as the worst angle on the path. The proposed approach also provides user-specified quality-based termination conditions.

I then present a method that addresses a continuous path representation, by employing piecewise Bezier curves for the path representation. In this way, the optimized paths guarantee C1 continuity and also enable taking into account curvature constraints, which are important on a number of applications. Given this representation, I then propose a new path optimization scheme based on convex optimization of piecewise quadratic Bezier paths. The proposed method targets a minimum required clearance from obstacles while minimizing path length and maximum curvature.The user is able to customize the objective function by assigning different weights to the clearance, length, and curvature terms.

Finally I introduce a priority-based approach to improve the application of the piecewise quadratic Bezier optimization scheme to multi-agent applications where a set of non-intersecting paths, or lanes, needs to be optimized.The proposed approach is called Multi-agent Interleaving Convex Optimization (MICO), where a priority-based approach is used to interleave the optimization of the individual lanes, such that convergence is achieved faster than alternative approaches. I present results comparing MICO to two other optimization strategies: the first is a Multi-agent Baseline Convex Optimization (MBCO) approach where lane optimization is interleaved without any particular priority, and the second method, called Piecewise Quadratic Bezier Curve Multi-agent Convex Optimization (MCO), applies the same optimization scheme to all the piecewise Quadratic Bezier paths simultaneously in a single optimization scheme. Users can still fine-tune the objective function by assigning different weights to clearance, length, and curvature terms, ensuring adaptability to various scenarios.

In conclusion, this work provides three new approaches to path optimization for multi-agent systems. The proposed methods address path optimization schemes that simultaneously optimizes for clearance, length, and curvature, providing flexibility and adaptability for various application requirements.This work also opens the door to the problem of developing multi-lane path planning and smoothing approaches, providing valuable tools for addressing certain types of multi-agent planning problems in robotics, autonomous vehicles, and simulated autonomous agents.