Transport management control apparatus and method for unmanned vehicle system

• US 5,625,559 A
• Filed: 06/22/1995
• Issued: 04/29/1997
• Est. Priority Date: 04/02/1993
• Status: Expired due to Fees

• Current Assignee: Asyst Shinko, Inc.
• Original Assignee: Shinko Electric Industries Company Limited (Fujitsu Limited)
• Inventors: Egawa, Takami
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Fiul, Dan
• Application Number:
  US08/493,783
• Time in Patent Office: 677 Days
• Field of Search: 246/3, 246/5, 364/436, 364/426.05, 364/424.02, 318/587, 395/500, 455/39
• US Class Current: 701/117
• CPC Class Codes: G05B 19/41895 using automatic guided vehicles [AGV] control of position or course of AGV's G05D1/00
• CPC Class Codes: G05B 2219/31003 Supervise route, reserve route and allocate route to vehicle, avoid collision
• CPC Class Codes: G05B 2219/32372 Petrinet, coloured, inhibitor arc, timed, object token Petrinet
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93
• CPC Class Codes: G05D 1/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/60 Electric or hybrid propulsion means for production processes

Abstract

The present invention provides a transport management method and apparatus for controlling the transport of a plurality of unmanned vehicles traveling over a travel grid formed from a plurality of nodes provided at stationary positions, and connection routes connecting the intervals between these nodes. The transport management apparatus according to the present invention has a first function for searching for a travel route for each unmanned vehicle in which an unmanned vehicle does not travel in the opposite direction over the same connection route as another unmanned vehicle and a second function for solving the progression impossibility of an unmanned vehicle using a node passing sequence change process, detour route search process or passing route search process, in the case when a progression impossibility of any unmanned vehicle is detected following simulation of the timed movements of each unmanned vehicle based on travel routes obtained by means of the aforementioned first function. As a result, the carrier efficiency therein is improved.

Claims

1. A transport management control apparatus which controls the transport of a plurality of unmanned vehicles traveling along travel routes formed by a plurality of connecting routes which connect nodes constituted by stopping positions of vehicles, said transport management control apparatus comprising:

route search means which searches for an optimal travel route which connects a present node to a target node having minimum cost for each unmanned vehicle by calculating costs of travel for possible transport intervals connecting said present node and said target node based on the positions of said nodes and the connections between said nodes; and

route arrangement means which, based on the results obtained by said route search means, for each unmanned vehicle, searches for opposite direction intervals which include the travel routes having mutually opposite directions from among said plurality of optimal travel routes, calculates the integral costs for each unmanned vehicle by totaling the costs of the opposite direction intervals of the travel routes of each unmanned vehicle, and then restricts the moving direction of the opposite direction intervals of the travel routes of the unmanned vehicles having the highest integral cost, making said intervals unidirectional;

wherein said route search means and said route arrangement means decide the optimal travel routes without conflicts for the unmanned vehicles by repeating the action of excluding said opposite direction intervals through the ordering of the integral costs of the opposite direction intervals until all of said opposite direction intervals are eliminated.

2. A transport management control apparatus according to claim 1 wherein said route arrangement means controls said route search means by varying the costs of said opposite direction intervals.

3. A transport management control apparatus which controls the transport of a plurality of unmanned vehicles traveling along travel routes formed from a plurality of connecting routes which connect nodes constituting vehicle stopping positions, said transport management control apparatus comprising:

first means which searches for an optimal travel route which connects a present node to a target node having minimum cost for each unmanned vehicle, by calculating costs of travel for possible transport intervals connecting said present node and said target node based on the positions of said nodes and the connections between said nodes, and based on the results, selects a travel interval having a specified moving direction by determining for each unmanned vehicle the travel intervals in which there are conflicts with the travel routes of other unmanned vehicles and totaling the costs of the conflicting intervals, then restricting the moving direction of the conflicting intervals of the unmanned vehicle having the highest cost to a specified direction, to determine the most appropriate travel routes having no conflicts by eliminating said conflicting intervals in the order of the costs of the conflicting intervals with respect to the unmanned vehicles; and

second means which simulates the temporal movements of each unmanned vehicle based on the travel routes determined by said first means, and if any of the unmanned vehicles are in a state of deadlock in which it is unable to advance, resolves the deadlock problem of said unmanned vehicle by;

adding a relief route to the travel route of said unmanned vehicle by moving another unmanned vehicle which has already completed its work to a node having the least cost for moving thereto,

changing the sequence in which unmanned vehicles pass through nodes by selecting a reservation sequence of nodes, containing unmanned vehicles which are not in a standby state, based on the number of passes which other unmanned vehicles make through the nodes,

offering a detour route by selecting an unmanned vehicle which is not in a standby state, prohibiting passage through a portion of the travel route of said unmanned vehicle, searching for a detour route to the next node in the travel route of said unmanned vehicle, and substituting the detour route as a new travel route for said unmanned vehicle to move to said next node, or

offering a passing route for temporarily yielding the right of way to an unmanned vehicle which is encountering the deadlock problem by temporarily moving an unmanned vehicle which is not in a standby state to a node having the least cost for moving thereto.

4. A transport management control method for controlling the transport of a plurality of unmanned vehicles traveling over travel routes formed from a plurality of connecting routes which connect nodes constituting stopping positions, said transport management control method comprising the steps of:

a. determining the optimal travel route of each of a plurality of the unmanned vehicles;

b. finding in the plurality of optimal travel routes obtained in step a., opposite direction intervals comprising travel routes having mutually opposite directions;

c. halting processing if opposite direction intervals are not present, and if opposite direction intervals are present, then calculating an integral cost for each unmanned vehicle by totaling the costs of the opposite direction intervals in the travel route of each unmanned vehicle;

d. applying a specified direction to an opposite direction interval on the travel route of the unmanned vehicle having the highest integral cost, so that this interval has one direction;

e. again determining the optimal travel routes of all unmanned vehicles, with the above-mentioned application of a specified direction to the travel routes; and

f. determining by the repetition of steps b., c., d. and e. optimal travel routes having no conflict.

5. A transport management control method for controlling the transport of a plurality of unmanned vehicles traveling over travel routes formed from a plurality of connecting routes which connect nodes constituting stopping positions, said transport management control method comprising the steps of:

a. determining the optimal travel route of each of a plurality of unmanned vehicles;

b. finding in the plurality of optimal travel routes obtained in step a. opposite direction intervals comprising travel routes having mutually opposite directions;

c. halting processing if opposite direction intervals are not present, and if opposite direction intervals are present, then calculating an integral cost for each unmanned vehicle by totaling the costs of the opposite direction intervals in the travel route of each unmanned vehicle;

d. applying a specified direction to an opposite direction interval on the travel route of the unmanned vehicle having the highest integral cost, so that this interval has one direction;

e. again determining the optimal travel routes of all unmanned carrier vehicles, with the above-mentioned application of a specified direction to the travel routes; and

f. determining by the repetition of steps b., c., d. and e. optimal travel routes having no conflict;

g. simulating the temporal movements of the unmanned vehicles in a travel grid based on said optimal travel routes;

h. if the simulation teaches that an unmanned vehicle has encountered a deadlock problem in which it is unable to advance, then adding a relief route to the travel route of said unmanned vehicle by moving another unmanned vehicle which has already completed its work to a node having the least cost for moving thereto;

i. if the deadlock problems of all unmanned vehicles encountering deadlock are not able to be resolved by the above-described step h., then changing the sequence in which unmanned vehicles pass through nodes by selecting a reservation sequence of nodes containing unmanned vehicles which are not in a standby state, based on the number of passes which other unmanned vehicles make through the nodes;

j. if the deadlock problem is not resolved by the above-described step i., then offering a detour route by selecting an unmanned vehicle which is not in a standby state, prohibiting passage through a portion of the travel route of said unmanned vehicle, searching for a detour route to the next node in the travel route of said unmanned vehicle, and substituting the detour route as a new travel route for said unmanned vehicle to move to said next node, or

k. if the deadlock problem is not resolved by the above-described step j., then offering a passing route for temporarily yielding the right of way to an unmanned vehicle which is encountering the deadlock problem, by temporarily moving an unmanned vehicle which is not in a standby state to a node having the least cost for moving thereto.

6. An optimal route determination apparatus comprising:

first cost calculation means, in which, with respect to a set of travel intervals connecting a first and second node which join one another and between which travel is possible, among a plurality of nodes on a travel route, calculates a first cost for each travel interval, based on the distance between the nodes and the movement time;

second cost calculation means, which, when a target node is directed, calculates the angular difference between the direction of the first node, as seen from the target node, and a prespecified direction, and calculates the angular difference between the direction of the second node, as seen from the target node, and prespecified direction, and based on these angular differences, calculates a second cost for each travel interval;

addition means for adding the results of the cost calculation of the first and second cost calculation means for each travel interval; and

route generation means, which, based on the added costs calculated by said addition means, selects the case in which the estimated value of the added costs of each travel interval has the smallest value as the optimal route from the departure node to the target node.