Path planning in an uncertain environment
First Claim
Patent Images
1. A method for controlling an object in an environment having N uncertainties comprising the steps ofa) starting from a plurality of configuration space representations, each configuration space representing cost to goal values for a possible environment of the object;
- b) combining the plurality of configuration space representations to yield a result configuration space representation;
c) finding a path based on the result configuration space representation;
d) controlling the object to follow the path.
1 Assignment
0 Petitions
Accused Products
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.
20 Citations
20 Claims
-
1. A method for controlling an object in an environment having N uncertainties comprising the steps of
a) starting from a plurality of configuration space representations, each configuration space representing cost to goal values for a possible environment of the object; -
b) combining the plurality of configuration space representations to yield a result configuration space representation; c) finding a path based on the result configuration space representation; d) controlling the object to follow the path. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
10. The method of claim 9 where p is a function of time.
-
11. The method of claim 9 where p is a function of location.
- 12. The method of claim 8 wherein the inserting step comprises calculating the average value according to the equation
- space="preserve" listing-type="equation">CG(at sensing point);
=CG(pathtail1)·
p(uncertainty present)+CG(pathtail2)·
p(uncertainty absent)+C
where CG is a function calculating cost to goal values;
pathtail1 is a variable representing the path from the sensing point to the goal in the presence of that which causes the uncertainty;
pathtail2 is a variable representing the path from the sensing point to the goal in the absence of that which causes the uncertainty;
p is a function calculating the probability of occurrence of its argument; and
C is a variable representing the cost of sensing presence or absence of the uncertainty. - space="preserve" listing-type="equation">CG(at sensing point);
-
-
13. The method of claim 12 where p is a function of time.
-
14. The method of claim 12 where p is a function of location.
-
15. The method of claim 12 where C is a function of time.
-
16. The method of claim 12 where C is a function of location.
-
17. The method of claim 1 wherein the finding step comprises
i) following direction arrow values in the result configuration space representation to a state which is either a goal or a sensing point where a corresponding uncertainty can be resolved; -
ii) determining whether the point is a goal; iii) if a result of the determining step is negative, sensing presence or absence of that which causes the corresponding uncertainty; and iv) replacing the result configuration space representation with a configuration space representation reflecting current knowledge.
-
-
18. The method of claim 17 further comprising iterating steps i)-iv) until a goal state is reached.
-
19. Apparatus for controlling the motion of an object in an environment which has uncertainties comprising:
-
a) means for combining a plurality of configuration space representations representing possible environments for the object to form a combined configuration space representation; b) means for storing the combined configuration space representation; b) means for calculating a path from the combined configuration space; and c) means responsive to the means for calculating for controlling the object to follow the path.
-
-
20. A method for controlling an object, of known position, to follow a path, the method comprising the steps of:
-
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; planning the path based on the representation; and
controlling the object to follow the path.
-
Specification