Static collision avoidance method for multiple automatically guided vehicles

• US 5,283,739 A
• Filed: 10/31/1988
• Issued: 02/01/1994
• Est. Priority Date: 08/30/1985
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Doty, Thomas J., Wand, Martin A., Summerville, David F., Williston, John P., Rice, Haradon J.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/265,206
• Time in Patent Office: 1,919 Days
• Field of Search: 364/424.02, 364/513, 364/444, 364/461, 180/168, 180/169, 395/80, 395/90
• US Class Current: 701/23
• 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

Abstract

The invention is a method of static collision avoidance for multiple automatically guided vehicles (AGVs) on bidirectional paths. It defines the allowable travel path for an AGV as a series of path segments through or between possible destination points (called nodes) which are defined for the factory floor. AGVs can move to or through any of these nodes and can arrive in a predetermined order, according to "rules" defined by the method. The invention provides better performance than conventional AGV systems by allowing multiple AGVs to coexist in the same pathways without collision or excessive queueing in systems which use free-roving AGVs having programmable bidirectional paths. This new ability maximizes the degrees of freedom of AGV movement while minimizing collisions and "deadlock."

Claims

1. A method of scheduling the routes for a plurality of AGVs, implementable in a computer, comprising:

(a) defining a plurality of paths, each of which comprises a beginning node and an ending node with a plurality of nodes in between, each path of the plurality of paths containing nodes common with other of said plurality of paths;

(b) determining which of said plurality of paths permit a given AGV to reach a destination node from an origin node;

(c) selecting and assigning one of said possible paths to said given AGV;

(d) calculating the times that each node along said assigned path would be occupied by said given AGV; and

(e) assigning each node along the assigned path to said given AGV for the calculated time needed to be occupied by said given AGV.

2. The method of claim 1, further comprising:

carrying out step (b) wherein said all possible paths do not include at least one node already assigned to another AGV for the same time period that said given AGV would need to occupy said at least one node.

3. The method of claim 2, further comprising:

wherein the selected and assigned path of step (c) is the possible path which would take said given AGV the shortest time period to traverse.

4. The method of claim 2, wherein:

steps (b) through (e) are carried out by a computer.

5. The method of claim 4, wherein:

step (e) includes the step of storing in computer memory, data indicating the various times that any given node would be occupied by any given AGV.