The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

PhD Thesis #8805

Title:Planning Automated Guided Vehicle Movements in a Factory.
Authors:Hwee Kaa,J
Date: 1988
Abstract:This dissertation examines the problem of planning automated guided vehicle (AGV) movement schedules in an automated factory. AGVs are used mainly for material delivery and will have an important role in linking "islands of automation" in automated factories. Their employment in this context requires the plans to be generated in a manner which supports temporal projection so that further planning in other areas is possible. Planning also occurs in a dynamic scenario - while some plans are being executed, planning for new tasks and replanning failing plans occur. Expeditious planning is thus important so that deadlines can be met. Furthermore dynamic replanning in a multi-agent environment has repercussions - changing one plan may require revision of other plans. Hence the issue of limiting the side effects of dynamic replanning is also considered. in dealing with these issues, the goals of this research are: (1) generate movement plans which can be executed efficiently; (2) develop fast algorithms for the recurrent subproblems viz task assignment and route planning; and (3) generate robust plans which tolerate execution deviations; this helps to minimize disruptive dynamic replanning with its tendency to initiate a chain reaction of plan revisions. Efficient movement plans mean more productive utilization of the AGV fleet and this objective can be realized by three approaches. First, the tasks are assigned to AGVs optimally using an improved implementation of the Hungarian method. Second, the planner computes shortest routes for the AGVs using a bidirectional heuristic search algorithm which is amenable to parallel implementation for further computational time reduction. Third, whenever AGVs are fortuitously predisposed to assist each other in task execution, the planner will generate gainful collaboration plans. Efficient algorithms have been developed in these areas. The algorithms for task assignment and route planning are also designed to be fast, in

[Search These Pages] [DAI Home Page] [Comment]