Assisted Shortest Path Problems and Global Optimization of Mixed-Integer Nonlinear Programs with Trigonometric Functions
Abstract
Cooperative behavior between mobile agents has received increasing interest in fields such as robotics, operations research, agriculture, and more. The use of multiple agents allows for a variety of problems to be addressed that a single agent could not complete otherwise. This dissertation considers a particular cooperative path planning problem referred to as the assisted shortest path problem (ASPP). In the ASPP, a primary agent, referred to as a convoy, wishes to travel from a starting location to a destination in minimum time. The environment the convoy travels in contains obstructions that impedes the movement of the convoy. Depending on the obstructions present, the convoy may or may not be capable of removing these obstructions on its own. In either case, a second agent, referred to as the support vehicle, is simultaneously deployed with the convoy. The support vehicle can remove obstructions that impede the convoy and aims to assist the convoy to its destination so the convoy may reach the destination in minimum time. The support vehicle may be allowed to terminate anywhere in the environment or may have a specified destination of its own. Multiple variations of the ASPP are presented and solved in the first half of this dissertation. In the second half, the problem of solving factorable mixed-integer nonlinear programs (MINLPs) with trigonometric terms is considered. An exact algorithm solving this class of problems is then presented. The problem of identifying reasonable weights to assign to the graph used to represent an instance of the ASPP may be posed as a MINLP with trigonometric terms and is used as a motivating example in the discussion of solving this class of MINLPs. This approach can be further extended to solve factorable MINLPs with differentiable, periodic terms.
Subject
Vehicle routingoptimization
robotics
graph theory
labeling algorithms
mathematical programming
Citation
Montez, Christopher M. (2023). Assisted Shortest Path Problems and Global Optimization of Mixed-Integer Nonlinear Programs with Trigonometric Functions. Doctoral dissertation, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /199177.