Document Type

Dissertation

Department

Mathematics (HMC)

Publication Date

1989

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 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 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 show 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.

Comments

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

Source: Author's submitted manuscript converted to pdf.

Advisor: Alan J. Goldman.

Rights Information

© 1989 Arthur T. Benjamin

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Download

Share

COinS