Stacker crane problem state space reduction.

摘要

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.;Two specific reductions are proposed in this thesis. Both are proven to preserve an optimal solution so that a solution on the reduced graph can be trivially converted to a solution on the original graph. The first reduction limits movement to a Hanan grid and resource drops to Hanan points. The second reduction recursively removes redundant corners, which is shown to preserve optimal paths also. This technique recognizes path symmetries and seeks to break them without compromising optimal solutions.