Turnpike structures for optimal maneuvers

Arthur Benjamin, Harvey Mudd College

Previously linked to as: http://ccdl.libraries.claremont.edu/u?/irw,445

Abstract

This dissertation is concerned with problems of optimally maneuvering a collection of objects ("pieces") from one location to another, subject to various restrictions on the allowable movements. We illustrate and prove that when the "distance" from the origin to the destination is large, and the movement rules and environment satisfy certain "homogeneity" properties, there exist near-optimal trajectories with very special (turnpike) structure. These results are obtained by representing the problem through a configuation graph. Here, we have a node for each configuration and an arc for every "different" legal move. Each arc is endowed with a scalar weight for the move's cost, and a vector weight for the move's "progress" towards the desired final placement. Optimal solutions to the maneuvering problem are shown to be equivalent to minimum-cost walks from the origin node to the destination node with a prescribed amount of progress. The turnpike solution to the graph problem (which spends most of its time going around at most m cycles) is constructed by utilizing a basic optimal solution of an associated linear program. We begin to explore potential applications of our configuration graph models to other types of problems (not all having to do with optimal maneuvering), and discuss further research directions.