Members:

Edward Tsang

Huosheng Hu

Tom Thurston

Hassan Rashidi

This page describes the auto-port project at University of Essex.

Overview of this research:
This research concerns itself with the scheduling of Autonomous Guided Vehicles (AGV’s) in a port. Port components that are relevant to our problem include berths, quay cranes, container storage areas, and a road network. A transportation requirement in a port is described by a set of jobs. Each job is described by (a) the source location of a container; (b) the time at which it is available for pick up; (c) the target location, where the container is to be delivered to; and (d) the time at which the container must arrive the target location. Any delay will incur heavy penalties. Given a number of AGVs and their availability, the task is to schedule the AGVs to meet the transportation requirements.

The auto-port scheduling problem defined above can be decomposed into two problems. At the strategic scheduling level, an AGV must be allocated to each job. Time taken for each job can be estimated, either from information on the map, or from past experience. Efficiency could be gained by minimizing traveling time (from the target location of the previous job to the source location of the next job) and waiting time.

At the fine-grained route-scheduling level, each AGV must find it way from the source to the target location. AGVs in a port have to share space resources (roads, junctions) in a safe manner. To minimize delay, a good schedule should avoid collision, congestion and deadlocks.

Development so far:
In the Essex auto-port project, we have developed a scheduler for strategic scheduling. The problem of allocating AGVs to jobs is formulated as a constraint satisfaction problem. At the first version of the strategic level, we assumed that there is no waiting time for the vehicle at the yard when it picks-up or drops-off the container. This assumption is legal since one yard crane is always available in the storage area and quay cranes are more critical than yard crane. The AGV allocation problem is an NP-complete problem. However, when the problem is over-constrained, finding the optimal solution with minimal penalty may be NP-complete. Our research in strategic scheduling is preliminary so far.

The current standard for fine-grained route-scheduling was developed during the MARTHA project. In this approach, which is known as the Plan Merging Paradigm, each vehicle is allowed to reserve resources (roads and junctions). Space is modeled in grids. Each AGV may reserve up to ‘n’ cells ahead of its route.

In our project, we adopt a strategy akin to the Plan Merging Paradigm. A multi-agent simulator has been implemented to help identifying the weaknesses of the Plan Merging Paradigm and address them. We found that if ‘n’ is too small, an AGV can not reach its top speed, since it can only travel as fast as it can safely break in time before a crossing which it does not own (hence not necessarily clear). Conversely, if ‘n’ is too large, then the vehicle prohibits other vehicles from using the resource unnecessarily. However, even if ‘n’ is set to an optimum setting for the AGV’s capabilities, there is no notion of priority and thus a vehicle with a heavily constrained deadline might have to wait for a vehicle with ample time to reach its destination.

Our strategy allows Scheduling By Addition And Insertion, (SBAAI). This approach allows vehicles with higher priority to insert their reservations before existing reservations. Our experiments have shown that this can increase the efficiency of AGV journeys, and thus the throughput of the entire dockyard.

Future Work:
Our future research is to study the dynamic scheduling problem, where the list of jobs change over time, AGVs may break down and travel time may vary from the expected time. The strategic scheduler will allocate jobs to AGVs, which will use the fine-grained route-scheduler to negotiate its way through the port. New jobs and delays are reported to the strategic scheduler, which may have to adjust its AGV allocations.