Physical Sciences and Mathematics Commons^™

Turnpike Structures For Optimal Maneuvers, Arthur T. Benjamin

All HMC Faculty Publications and Research

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 configuration 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 …