Space partitioning for motion planning

Patent metadata

Field	Value
Publication number	US-2017308102-A1
Application number	US-201515521544-A
Country	US
Kind code	A1
Filing date	Oct 28, 2015
Priority date	Oct 28, 2014
Publication date	Oct 26, 2017
Grant date	—

Abstract

An aspect includes space partitioning for vehicle motion planning. A plurality of obstacle data is analyzed to determine a plurality of obstacle locations in a configuration space of a vehicle. A partitioning of the configuration space is performed to compute a skeletal partition representing a plurality of obstacle boundaries based on the obstacle locations. The skeletal partition is used to preferentially place a plurality of samples by a sampling-based motion planner. At least one obstacle-free path is output by the sampling-based motion planner based on the samples.

First claim

1 . A method of space partitioning for motion planning, the method comprising:
analyzing a plurality of obstacle data to determine a plurality of obstacle locations in a configuration space of a vehicle; performing a partitioning of the configuration space to compute a skeletal partition representing a plurality of obstacle boundaries based on the obstacle locations; using the skeletal partition to preferentially place a plurality of samples by a sampling-based motion planner; and outputting at least one obstacle-free path by the sampling-based motion planner based on the samples.

2 . The method of claim 1 , wherein the partitioning of the configuration space is performed by computing a medial axis between the obstacle locations as the skeletal partition.

3 . The method of claim 1 , wherein the partitioning of the configuration space is performed by computing Voronoi tessellation edges of the obstacle locations as the skeletal partition.

4 . The method of claim 1 , wherein the configuration space is partitioned into three-dimensional cells defined as free space or obstacles.

5 . The method of claim 1 , further comprising:
applying a weighted distribution to randomly place higher percentage of samples closer to the skeletal partition.

6 . The method of claim 1 , further comprising:
applying a cost function to determine a lowest cost path of the at least one obstacle-free path.

7 . The method of claim 6 , further comprising:
placing un-weighted random samples in the configuration space to search for a lower cost path based on identifying the at least one obstacle-free path.

8 . The method of claim 1 , wherein the method is performed by a system of the vehicle.

9 . The method of claim 8 , wherein the obstacle data are acquired from a combination of a priori terrain data and sensor data of the vehicle.

10 . A motion planning system for a vehicle, the motion planning system comprising:
a processor; and memory having instructions stored thereon that, when executed by the processor, cause the motion planning system to: analyze a plurality of obstacle data to determine a plurality of obstacle locations in a configuration space of the vehicle; perform a partitioning of the configuration space to compute a skeletal partition representing a plurality of obstacle boundaries based on the obstacle locations; use the skeletal partition to preferentially place a plurality of samples by a sampling-based motion planner; and output at least one obstacle-free path by the sampling-based motion planner based on the samples.

11 . The motion planning system of claim 10 , wherein the partitioning of the configuration space is performed by computing a medial axis between the obstacle locations as the skeletal partition.

12 . The motion planning system of claim 10 , wherein the partitioning of the configuration space is performed by computing Voronoi tessellation edges of the obstacle locations as the skeletal partition.

13 . The motion planning system of claim 10 , wherein the instructions further cause the motion planning system to apply a weighted distribution to place higher percentage of samples closer to the skeletal partition.

14 . The motion planning system of claim 10 , wherein the instructions further cause the motion planning system to:
apply a cost function to determine a lowest cost path of the at least one obstacle-free path; and place un-weighted random samples in the configuration space to search for a lower cost path based on identifying the at least one obstacle-free path.

15 . The motion planning system of claim 10 , wherein the obstacle data are acquired from a combination of a priori terrain data and sensor data of the vehicle.

Assignees

• Sikorsky Aircraft Corp

Inventors

• Sane Harshad S
• Derenick Jason C
• Englot Brendan J
• Frewen Thomas A

Classifications

• G05D1/10 Primary

  Simultaneous control of position or course in three dimensions (G05D1/12 takes precedence) · CPC title

• G01C21/34

  Route searching; Route guidance · CPC title

• G05D1/106 Primary

  Change initiated in response to external conditions, e.g. avoidance of elevated terrain or of no-fly zones · CPC title