Path planning in an uncertain environment

• US 5,764,510 A
• Filed: 05/30/1995
• Issued: 06/09/1998
• Est. Priority Date: 04/11/1990
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Dorst, Leendert, Cameron, Alexander John
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US08/453,424
• Time in Patent Office: 1,106 Days
• Field of Search: 364/148, 364/167.01, 364/424.01, 364/424.02, 364/424.2, 364/461, 364/460, 340/932.2, 901/1, 901/50, 318/587, 318/568.12, 395/80, 395/90, 395/919, 395/902-904, 395/912, 701/23, 701/24, 701/25, 701/26, 701/27, 701/301, 701/300
• US Class Current: 700/56
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40448 Preprocess nodes with arm configurations, c-space and planning by connecting nodes
• CPC Class Codes: G05B 2219/40465 Criteria is lowest cost function, minimum work path
• CPC Class Codes: G05B 2219/40471 Using gradient method
• CPC Class Codes: G05B 2219/45131 Turret punch press
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G06F 2111/08 Probabilistic or stochastic CAD
• 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

Configuration spaces, representing alternate possibilities for an environment in which an object is to move, are combined to create a probabilistic representation of all of the alternate possibilities. The probabilistic representation is used to plan optimal motion, with uncertainties being resolved at sensing points.

Claims

1. Apparatus for controlling an object of known position to follow a path, the apparatus comprising

means for storing a representation of a current or future environment of the object, the representation including a configuration space including a plurality of states, each state including a cost to goal value, at least one cost to goal value being based on a probability of a condition occurring in that environment, wherein the existence of the condition is not known with certainty;

means for planning the path based on the representation; and

means for controlling the object to follow the path.

2. The apparatus of claim 1 further comprising

means for starting from a plurality of configuration space representations, each configuration space representation including cost to goal values for a possible environment of the object;

means for combining the plurality of configuration space representations to yield a final configuration space representation.

3. The apparatus of claim 1 wherein the condition is an obstacle.

4. The apparatus of claim 3 wherein the obstacle has a known probability of being present.

5. The apparatus of claim 1 wherein the condition is a goal.

6. The apparatus of claim 5 wherein the goal has a known probability of being present.

7. The apparatus of claim 2 wherein the means for starting initializes 2^N configuration space representations, each configuration space representation including cost to goal values for a situation in which single respective permutation of conditions is present, wherein N is a number of conditions in the environment which are not known with certainty.

8. The apparatus of claim 7 wherein the means for combining, for N iterations, combines the configuration space representations in groups of size two multiplied by the number of iterations.

9. The apparatus of claim 8 wherein the means for combining

for each state having a respective common cost to goal value in all of the configuration space representations in a current group, sets a value of a corresponding state in an output configuration space representation to the respective common value;

for each state where cost to goal values differ between the configuration space representations in the current group, an which is a sensing location, inserts an average cost to goal value in a corresponding state in the output configuration space representation; and

propagates cost waves sin the output configuration space representation from the states affected by the insertion and setting.

10. The apparatus of claim 9 wherein the combining means, in order to effect the insertion, comprises means for calculating the average value according to the equation

11. The apparatus of claim 10 wherein p is a function of time.

12. The apparatus of claim 10 wherein p is a function of location.

13. The apparatus of claim 9 wherein the combining means, in order to effect the insertion, comprises means for calculating the average value according to the equation

14. The apparatus of claim 13 wherein p is a function of time.

15. The apparatus of claim 13 wherein p is a function of location.

16. The apparatus of claim 13 wherein C is a function of time.

17. The apparatus of claim 13 wherein C is a function of location.

18. The apparatus of claim 1 wherein the means for planning comprises

means for following direction arrow values in the configuration space representation to a state which is either a goal or a sensing point where a corresponding uncertainty can be resolved;

means for determining whether the point is a goal;

means for, if a result of the determining step is negative, sensing presence or absence of that which causes the corresponding uncertainty; and

means for replacing the configuration space with a configuration space reflecting current knowledge.

19. The apparatus of claim 18 further comprising iterating until a goal is reached.

20. Apparatus for controlling an object of known position to follow a path, the apparatus comprising

means for storing a representation of a current or future environment of the object, in which environment the position of the object is taken as known, which representation includes values based on probabilities of conditions occurring in that environment, wherein the existence of said conditions is not known with certainty;

means for planning the path based on the representation; and

means for controlling the object to follow the path.

21. The apparatus of claim 20 wherein the object is a motor vehicle.

22. The apparatus of claim 21 wherein one of the conditions is a traffic condition.

23. The apparatus of claim 22 wherein the traffic condition is a future traffic condition at a future location of the vehicle.