Date of Award

Spring 2013

Project Type

Thesis

Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Wheeler Ruml

Abstract

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.

Download

Share

COinS