TIME-AUGMENTED OPTIMIZATION IN CONVEX SETS

Abstract

This research extends previous work on the shortest path algorithm within convex sets by incorporating position, velocity, and time constraints. Building on the foundational principles from prior studies by Marcucci et al. [1], which formulated a general framework for the shortest path problem in graphs of convex sets, this study addresses the added complexities introduced by velocity and time constraints. While the previous work focused on path optimization in convex graphs, this paper expands the formulation to account for these additional dynamic factors. The primary objective of this optimization is to minimize the distance traveled within convex sets while adhering to position, velocity, and time constraints in 3D space. This is particularly relevant for applications such as robotic path planning, autonomous vehicles, and other fields where efficient and precise path planning is essential. To achieve this, we first formulate a non-convex mixed-integer program. Then, through several steps, including the use of set-based relaxation (SBR)to relax it and convert it into a convex program. Velocity and time constraints are imposed through this formulation, resulting in tighter convex set bounds that provide more accurate results, making it suitable for handling the complexities of 3D space. The outcome of this research is a comprehensive formulation that demonstrates the impact of several time-bound constraints on the optimization objective and running time, considering multiple convex sets.