Path planning with transition changes

• US 5,083,256 A
• Filed: 10/17/1989
• Issued: 01/21/1992
• Est. Priority Date: 03/09/1988
• Status: Expired due to Term

• Current Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Original Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Inventors: Trovato, Karen I., Dorst, Leendert
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US07/422,930
• Time in Patent Office: 826 Days
• Field of Search: 364/513, 364/148, 364/424.02, 364/436-438, 364/444, 364/461, 364/167.01, 364/200 MS File, 364/474.2
• US Class Current: 700/56
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 19/4061 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/35415 3-D three dimension, space input, spaceball
• CPC Class Codes: G05B 2219/40443 Conditional and iterative planning
• CPC Class Codes: G05B 2219/40476 Collision, planning for collision free path
• CPC Class Codes: G05B 2219/49143 Obstacle, collision avoiding control, move so that no collision occurs
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A configuration space is used for path planning and for controlling the motion of an object. The configuration space includes states which contain cost to goal and direction arrow values. These values indicate a path or absence of a path from the states to at least one goal state. The configuration space is differentially updated after a cost to goal or direction arrow value is changed.

Claims

1. A method for controlling an object to follow a path comprising the steps of:

a) maintaining a stored configuration space having cost to goal and direction arrow values indicating the path or absence thereof from at least one state in the configuration space to at least one goal state in the configuration space;

b) receiving data indicating a change in a transition between states in the configuration space; and

c) differentially updating the configuration space to reflect the change, so that at least one cost to goal or one direction arrow value is changed; and

d) controlling the object to follow a path indicated by the undated configuration space.

2. A method for controlling an vehicle to follow a path comprising the steps of:

a) maintaining a stored configuration space having cost to goal and direction arrow values indicating the path of absence thereof from at least one state in the configuration space to at least one goal state in the configuration space, which configuration space represents traffic conditions on a plurality of streets;

b) receiving data indicating a change in a transition between states in the configuration space, which change represents a change in traffic conditions in one lens of one of the plurality of streets;

c) differentially updating the configuration space to reflect the change, so that at least one cost to goal or one direction arrow value is changed; and

d) controlling the vehicle to follow a path indicated by the updated configuration space.