Date of Award
Program or Major
Master of Science
Many resource delivery problems, from delivery vehicle routing to circuit board assembly, can be expressed as stacker-crane problems (SCPs). In SCPs, a single agent must transfer resources from their starting locations to goal locations by traversing a graph. These problems have been split into many categories based on their graph structure and other problem properties. This thesis examines preemptive stacker-crane problems on four-connected grids, which are common graphs in motion planning domains. A wealth of research has already been done on motion planning on graphs, both for optimal and suboptimal solutions. This thesis focuses on reducing the number of vertices in the graph and the number of actions available at each vertex rather than presenting a specific solution, which allows for any solver to be used on the reduced graph.
Kreimendahl, Frank, "Stacker crane problem state space reduction" (2013). Master's Theses and Capstones. 793.