METHOD AND DEVICE FOR THREE-DIMENSIONAL PATH PLANNING TO AVOID OBSTACLES USING MULTIPLE PLANES

• US 20090228205A1
• Filed: 03/10/2008
• Published: 09/10/2009
• Est. Priority Date: 03/10/2008
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Lautenschlager, Eric, Ariyur, Kartik B., Elgersma, Michael R.
• Granted Patent: US 8,078,399 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G06G 7/78 for direction-finding, locating, distance or velocity measuring, or navigation systems

Abstract

An obstacle-avoidance-processor chip for three-dimensional path planning comprises an analog processing circuit and at least two analog-resistive-grid networks. The analog processing circuit is communicatively coupled to receive data from an inertial measurement unit and from at least one obstacle-detection sensor. The analog processing circuit is configured to construct a three-dimensional obstacle map of an environment based on the received data. The at least two analog-resistive-grid networks are configured to map obstacles in at least two respective non-parallel planes in the constructed three-dimensional obstacle map. The at least two analog-resistive-grid networks form a quasi-three-dimensional representation of the environment. The obstacle-avoidance-processor chip generates information indicative of a three-dimensional unobstructed path in the environment based on the obstacle maps.

Claims

1. An obstacle-avoidance-processor chip for three-dimensional path planning, the obstacle-avoidance-processor chip comprising:

an analog processing circuit communicatively coupled to receive data from an inertial measurement unit and from at least one obstacle-detection sensor, the analog processing circuit configured to construct a three-dimensional obstacle map of an environment based on the received data; and

at least two analog-resistive-grid networks, configured to map obstacles in at least two respective non-parallel planes in the constructed three-dimensional obstacle map, and form a quasi-three-dimensional representation of the environment;

wherein the obstacle-avoidance-processor chip generates information indicative of a three-dimensional unobstructed path in the environment.

2. The chip of claim 1, wherein the at least two analog-resistive-grid networks comprise:

a first high-density analog-resistive-grid network configured to map obstacles in a first plane in which the vehicle is moving; and

a second low-density analog-resistive-grid network configured to map obstacles in a second plane that includes a line indicative of a heading of the vehicle.

3. The chip of claim 2, wherein the second plane is orthogonal to the first plane.

4. The chip of claim 2, wherein the second plane changes as a direction of propagation of the vehicle changes.

5. The chip of claim 1, wherein a first selected-potential on the analog-resistive-grid networks indicates an obstacle, a second selected potential having a value less than the first selected potential indicates a destination, and a currently-planned-unobstructed path is generated following a potential gradient from a potential of a current location of the vehicle as represented by a point on the analog-resistive-grid networks.

6. The chip of claim 1, wherein the analog processing circuit comprises an analog stereo processing circuit configured to construct the environment by fusing information indicative of the currently-planned-unobstructed path with sensor data received from the inertial measurement unit and at least two obstacle-detection sensors that are spatially offset from each other.

7. The chip of claim 1, wherein the analog processing circuit is communicatively coupled to receive data from a global positioning system.

8. The chip of claim 1, further comprising:

at least one first input interface configured to receive sensor data indicative of obstacles in the environment from the at least one obstacle-detection sensor; and

a second input interface to receive data indicative of a relative position of a vehicle in the environment from the inertial measurement unit.

9. An integrated module for three-dimensional path planning, the integrated module comprising:

an inertial measurement unit;

at least one obstacle-detection sensor; and

an obstacle-avoidance-processor chip communicatively coupled to receive data from the inertial measurement unit and the obstacle-detection sensor, wherein the obstacle-avoidance-processor chip generates obstacle maps based on inputs from the inertial measurement unit and the obstacle-detection sensor to provide a quasi-three-dimensional representation of a three-dimensional environment, and wherein the obstacle-avoidance-processor chip generates information indicative of at least one unobstructed path in the environment based on the obstacle maps.

10. The integrated module of claim 9, wherein the obstacle-avoidance-processor chip comprises:

an analog processing circuit communicatively coupled to receive data indicative of a relative position of a vehicle in the environment from the inertial measurement unit and to receive sensor data indicative of obstacles in the environment from at least one obstacle-detection sensor, the analog processing circuit configured to construct a three-dimensional environment based on the received data; and

at least two analog-resistive-grid networks configured to map obstacles in at least two respective non-parallel planes, wherein the at least two analog-resistive-grid networks represent at least two respective cross-sections of the constructed three-dimensional obstacle map, wherein the at least two respective cross-sections of the constructed three-dimensional obstacle map form the quasi-three-dimensional representation of the environment.

11. The integrated module of claim 10, wherein the received sensor data is used to update voltage points on the at least two analog-resistive-grid networks.

12. The integrated module of claim 9, wherein the at least one obstacle-detection sensor comprises at least one optical imaging system or at least one radar imaging system.

13. The integrated module of claim 9, wherein the inertial measurement unit senses a heading and orientation of a vehicle housing the integrated module.

14. The integrated module of claim 9, wherein the information indicative of at least one unobstructed path is implemented to determine a velocity of a vehicle housing the integrated module.

15. The integrated module of claim 9, wherein the obstacle-detection sensor iteratively sends range data and probability-of-collision data to the obstacle-avoidance-processor chip, and wherein the obstacle-avoidance-processor chip generates a pre-selected voltage on at least one obstacle map when a probability-of-collision exceeds a pre-selected threshold.

16. A method of planning an unobstructed three-dimensional path for a vehicle, the method comprising:

receiving information indicative of the environment in which the vehicle is moving;

constructing a three-dimensional obstacle map of the environment based on the information indicative of the environment;

executing software to solve Laplacian equations for a high-density analog-resistive-grid network;

executing software to solve Laplacian equations for at least one lower-density analog-resistive-grid network; and

producing an unobstructed three-dimensional path for the vehicle to follow based on the executions of the software to solve Laplacian equations.

17. The method of claim 16, further comprising:

extracting at least a first plane and a second plane non-parallel to the first plane from the constructed three-dimensional obstacle map, wherein the first plane is indicative of the plane in which the vehicle is moving, and wherein the second plane is indicative of a plane containing a line indicative of a heading of the vehicle;

mapping obstacles in a first plane based on the executing software to solve Laplacian equations for the high-density analog-resistive-grid network; and

mapping obstacles in a second plane based on executing software to solve Laplacian equations for the at least one lower-density analog-resistive-grid network, wherein the mapped obstacles are represented as a selected voltage within the high-density analog-resistive-grid network and the at least one lower-density analog-resistive-grid network.

18. The method of claim 17, further comprising:

reconstructing the three-dimensional obstacle map based on receiving updated information indicative of the environment;

updating voltage points on at least one of the lower-density analog-resistive-grid network and the high-density analog-resistive-grid network responsive to reconstructing the three-dimensional obstacle map; and

producing an updated unobstructed three-dimensional path for the vehicle to follow based on the executions of the software to solve Laplacian equations.

19. The method of claim 17, further comprising:

updating the map to reflect a motion of the vehicle.

20. An obstacle-avoidance-processor chip for three-dimensional path planning, the obstacle-avoidance-processor chip comprising:

an analog processing circuit communicatively coupled to receive data from an inertial measurement unit and from at least one obstacle-detection sensor, the analog processing circuit configured to construct a three-dimensional environment based on the received data; and

a field programmable gate array implementing a Laplacian algorithm to map obstacles in at least two non-parallel planes representative of at least two respective cross-sections of the constructed three-dimensional obstacle map;

wherein the at least two respective cross-sections of the constructed three-dimensional obstacle map form a quasi-three-dimensional representation of the environment, and wherein the obstacle-avoidance-processor chip generates information indicative of an unobstructed path in the environment based on the obstacle maps.