Method and system for fast precise path planning

Patent metadata

Field	Value
Publication number	US-9946979-B2
Application number	US-99681809-A
Country	US
Kind code	B2
Filing date	Jun 19, 2009
Priority date	Jun 26, 2008
Publication date	Apr 17, 2018
Grant date	Apr 17, 2018

Abstract

A system ( 200 ) executes a method ( 130 - 180 ) to produce an optimal path for any type of path planning application. In operation, the system ( 200 ) constructs a configuration space node structure representing a discretized configuration space including a plurality of states characterized by one or more parameters, and augments the configuration space node structure with discrete parameter values explicitly quantifying each node of the configuration space node structure and/or with heuristic values serving as a search guide through a free space region of the discretized configuration space.

First claim

The invention claimed is:

1. A method for planning a path according to a path plan application, the method, comprising:
constructing a configuration space node structure within a data storage medium, the configuration space node structure representing a discretized configuration space including a plurality of nodes characterized by at least one parameter,
wherein the discretized configuration space is one of a two-dimensional discretized configuration space or a three-dimensional discretized configuration space; and

augmenting the configuration space node structure as constructed within the data storage medium with discrete parameter values explicitly quantifying at least one of a location and an orientation of each node of the configuration space node structure.

2. The method of claim 1 , wherein the discrete parameter values are derived from a discrete sampling of a neighborhood corresponding to the discretized configuration space.

3. The method of claim 1 , further comprising:
propagating cost waves in the configuration space node structure to fill at least a portion of the configuration space node structure with cost values as a function of the discrete parameter values.

4. The method of claim 3 , wherein the configuration space node structure is augmented with the discrete parameter values prior to the propagation of the cost waves in the configuration space node structure.

5. The method of claim 3 , wherein the configuration space node structure is augmented with the discrete parameter values in response to the propagation of the cost waves in the configuration space node structure.

6. The method of claim 1 , further comprising:
propagating cost waves in the configuration space node structure to fill at least a portion of the configuration space node structure with heuristic values representing a search guide through a free space region of the discretized configuration space.

7. The method of claim 6 , wherein the heuristic values are derived from a neighborhood configuration connecting each node of the configuration space node structure corresponding to the free space region of the discretized configuration space.

8. A system, comprising:
a data storage medium and a data processing device for planning an optimal path according to a path planning application;
wherein the data processing device is operable to construct a configuration space node structure within the data storage medium, the configuration space node structure representing a discretized configuration space including a plurality of nodes characterized by at least one parameter;
wherein the discretized configuration space is one of a two-dimensional discretized configuration space or a three-dimensional discretized configuration space; and
wherein the data processing device is further operable to augment a construction of the configuration space node structure within the data storage medium with discrete parameter values explicitly quantifying at least one of a location and an orientation of each node of the configuration space node structure.

9. The system of claim 8 , wherein the data processing device is further operable to derive the discrete parameter values from a discrete sampling of a neighborhood corresponding to the discretized configuration space.

10. The system of claim 8 , wherein the data processing device is further operable to propagate cost waves in the configuration space node structure to fill at least a portion of the configuration space node structure with cost values as a function of the discrete parameter values.

11. The system of claim 10 , wherein the configuration space node structure is augmented with the discrete parameter values prior to the propagation of the cost waves in the configuration space node structure.

12. The system of claim 10 , wherein the configuration space node structure is augmented with the discrete parameter values in response to the propagation of the cost waves in the configuration space node structure.

13. The system of claim 8 , wherein the data processing device is further operable propagate cost waves in the configuration space node structure to fill at least a portion of the configuration space node structure with heuristic values representing a search guide through a free space region of the discretized configuration space.

14. The system of claim 13 , wherein the heuristic values are derived from a neighborhood configuration connecting each node of the configuration space node structure corresponding to the free space region of the discretized configuration space.

15. A data processing device, comprising:
a setup unit and a path planning unit for planning an optimal path according to a path planning application;
wherein the setup unit is operable to construct a configuration space node structure within a data storage medium, the configuration space node structure representing a discretized configuration space including a plurality of nodes characterized by at least one parameter;
wherein the discretized configuration space is one of a two-dimensional discretized configuration space or a three-dimensional discretized configuration space; and
wherein at least one of the setup unit and the path planning unit is operable to augment construction of the configuration space node structure within the data storage medium with discrete parameter values explicitly quantifying at least one of a location and an orientation of each node of the configuration space node structure.

Assignees

• Trovato Karen Irene
• Popovic Aleksandra
• Koninklijke Philips Nv

Inventors

• Trovato Karen Irene
• Popovic Aleksandra

Classifications

• A61B2017/3443

  with means for adjusting the length of a cannula · CPC title

• A61B17/3421

  Cannulas · CPC title

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title