Differential budding: method and apparatus for path planning with moving obstacles and goals
First Claim
Patent Images
1. A method for planning a path for an object to follow in a task space in which there has been a change in conditions comprising the steps of:
- a. starting from an initialized configuration space;
b. identifying a perimeter of a region in the configuration space which is effected by the change in conditions; and
c. propagating cost waves from the perimeter using a space variant metric to create updated direction errors values corresponding to the change in conditions,wherein the method is part of a method for controlling the motion of the object, comprising the further steps of;
a. using the updated direction arrows values to find a least cost path a start point to a goal point in the task space;
b. providing at least one point on the path; and
c. controlling the object to travel to the at least one point.
1 Assignment
0 Petitions
Accused Products
Abstract
A method is presented for path planning after changes in task space. In one embodiment, the method is applied to planning a path for a robot arm. The method identifies areas in the configuration space which are affected by the changes in task space. Cost waves can then be repropagated in these affected areas to allow for planning in N dimensions and using space variant metrics. The method is also adapted to use in the presence of phantom obstacles.
48 Citations
40 Claims
-
1. A method for planning a path for an object to follow in a task space in which there has been a change in conditions comprising the steps of:
-
a. starting from an initialized configuration space; b. identifying a perimeter of a region in the configuration space which is effected by the change in conditions; and c. propagating cost waves from the perimeter using a space variant metric to create updated direction errors values corresponding to the change in conditions, wherein the method is part of a method for controlling the motion of the object, comprising the further steps of; a. using the updated direction arrows values to find a least cost path a start point to a goal point in the task space; b. providing at least one point on the path; and c. controlling the object to travel to the at least one point. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A method for in which planning a path for an object to follow in a task space there has been a change in conditions comprising the steps of:
-
a. starting from a configuration space containing direction arrows values and corresponding to the task space as it existed prior to the change in conditions; and b. differentially budding an area in the configuration space which is affected by the change in conditions to obtain updated cost values, wherein differentially budding comprises the steps of; i. identifying a perimeter of a region configuration space which is affected by the change in conditions; and
d costii. budding from the perimeter to create update values corresponding to the change in conditions, wherein budding comprises; (A) exploring all neighbors of a state in the configuration space; (B) improving neighbors of the state by assigning appropriate values of cost to goal and direction arrows to the state; (C) adding improved neighbors to a storage data structure; and (D) repeating (b) (ii) (A)-(b) (ii) (D) for all states in the storage data structure, wherein the method is part of a method for controlling the motion of the object, comprising the further steps of; a. using the updated cost values to find a least cost path from a starting point to a goal point in the task space; b. providing at least one point on the path; and c. controlling the object to move to the at least one point. - View Dependent Claims (30)
-
-
31. A method for planning a path for an object to follow in a task space in which there has been a change in conditions and for controlling the object to follow the path comprising the steps of:
-
a. starting from an initialized configuration space; b. identifying a perimeter of a region in the configuration space which is affected by the change in conditions; c. repropagating cost waves from the perimeter to create an updated configuration space; and d. controlling the object to follow a new path indicated by the updated configuration space. - View Dependent Claims (32)
-
-
33. A method for planning a path for a robot to follow in a task space in which there has been a change in conditions, comprising the steps of:
-
a. starting from an initialized configuration space; b. identifying a perimeter of a region in the configuration space which is affected by the change in conditions; and c. repropagating cost waves from the perimeter to create an updated configuration space wherein (a) the robot is a robot arm; (b) the method is part of a method for controlling the motion of the robot arm; (c) during the starting step, the configuration space contains direction arrows values which reflect propagation in response to a metric which minimizes motion of an end effector of the robot; and (d) the method further comprises the step of controlling the robot arm to follow a new path indicated by the configuration space.
-
-
34. Apparatus for controlling motion of a robot, comprising:
-
(a) a configuration space comprising a plurality of states filled with direction arrows values and post to goal values and representing a task space of the robot according to a plurality of perimeters of the robot; (b) means for signifying in the configuration space a change in conditions in the task space; (c) means for identifying a perimeter of a region in the configuration space which is affected by the change in conditions; (d) means for propagating cost waves from the perimeter using a space variant metric to create updated direction arrows values and cost to goal values corresponding to the change in conditions; and (e) means for controlling the robot to follow a path indicated by the updated direction arrows values. - View Dependent Claims (35, 36, 37, 38, 39, 40)
-
Specification