Planning automated guided vehicle movements in a factory
View/ Open
Date
1988Author
Kwa, James Boon Hwee
Metadata
Abstract
This dissertation examines the problems 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 collaborative plans. Efficient
algorithms have been developed in these areas. The algorithms for task assignment and
route planning are also designed to be fast, in keeping with the objective of expeditious
planning.
Robust plans can be generated using the approach of tolerant planning. Robustness is
achieved in two ways: (1) by being tolerant of an AGV's own execution deviations; and
(2) by being tolerant of other AGVs' deviant behaviour. Tolerant planning thus defers
dynamic replanning until execution errors become excessive. The underlying strategy is
to provide more than ample resources (time) for AGVs to achieve various subgoals. Such
redundancies aggravate the resource contention problem. To solve this, an iterative
negotiation model is proposed. During negotiations, AGVs yield in turn to help
eliminate the conflict. The negotiation behaviour of each is governed by how much spare
resources each has and tends towards intransigence as the bottom line is approached. In
this way, no AGV will jeopardize its own plan while cooperating in the elimination of
conflicts. By gradual yielding, an AGV is also able to influence the other party to yield
more if it can, therein achieving some fairness. The model has many of the
characteristics of negotiation acts in the real world (e.g. skilful negotiation,
intransigence, selfishness, willingness to concede, nested negotiations).
Collections
Related items
Showing items related by title, author, creator and subject.
-
Automated reasoning with uncertainties
Corrêa da Silva, Flávio S. (The University of Edinburgh, 1993) -
Providing Automated Semantic Support for Software Agents in Spatial Decision Support Systems
Li, Sen (The University of Edinburgh, 2008-12-05)Spatial Decision Support System(SDSS) is a software system that aimed at assisting decision-makers generate and evaluate alternative solutions to semi and unstructured spatial problems through the integration of spatial ... -
A Comparison of Automated and Rating-Based Methods of Estimating Coherence in Natural Speech
Loginova, Ekaterina (The University of Edinburgh, 2016)