Straight line path planning

• US 9,164,510 B2
• Filed: 07/13/2013
• Issued: 10/20/2015
• Est. Priority Date: 07/13/2012
• Status: Active Grant

• Current Assignee: International Electronic Machines Corp.
• Original Assignee: International Electronic Machines Corp.
• Inventors: Mian, Zahid F., Berard, Brian M., Spoor, Ryk E.
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): SMITH-STEWART, DEMETRA R
• Application Number:
  US13/941,482
• Publication Number:
  US 20140018996A1
• Time in Patent Office: 829 Days
• US Class Current: 1/1
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A solution for navigating a vehicle is provided. The vehicle is navigated from a start location to a target location using a set of linear paths. A current linear path is identified between a current location of the vehicle and the target location. At least a portion of the current linear path is evaluated for a presence of an obstacle. In response to no obstacle being present along the current linear path, the vehicle is instructed to travel along the current linear path to the target location. In response to an obstacle being present, the vehicle is instructed to travel along a different linear path from the current location to an intermediate location, which is selected based on an extent of the obstacle and the current linear path. The process can be repeated until the vehicle arrives at the target location.

Claims

1. A method comprising:

a computer system automatically navigating a vehicle from a current location to a target location, wherein the navigating includes;

selecting a set of linear paths for the vehicle to travel between the current location and the target location, the selecting including, for each linear path in the set of linear paths;

identifying a current linear path between the current location and the target location;

evaluating a set of cells along the current linear path for a presence of an obstacle;

instructing the vehicle to travel along the current linear path in response to evaluating all cells between the current location and the target location along the current linear path as not including an obstacle; and

in response to evaluating a cell in the set of cells as including an obstacle;

determining a center of mass corresponding to an extent of the obstacle;

identifying a set of potential locations based on the center of mass, a line through the center of mass and perpendicular to the current linear path, and the extent of the obstacle;

selecting a potential location in the set of potential locations as the intermediate location based on the extent of the obstacle and the current linear path; and

instructing the vehicle to travel along a distinct linear path from the current location to the intermediate location.

2. The method of claim 1, wherein each cell corresponds to a minimal navigable area selected based on at least one of:

a size or a maneuverability of the vehicle.

3. The method of claim 1, wherein the selecting further includes, in response to evaluating a cell in the set of cells as including an obstacle, inflating the extent of the obstacle based on a size of the vehicle, wherein the determining a center of mass and the identifying a set of potential locations uses the inflated extent of the obstacle.

4. The method of claim 3, wherein the selecting further includes, in response to evaluating a cell in the set of cells as including an obstacle, calculating a cost for each of a plurality of potential locations in the set of potential locations, wherein the intermediate location corresponds to the potential location having a lowest cost.

5. The method of claim 1, the navigating further including obtaining data corresponding to a set of known attributes for the obstacle, wherein the extent of the obstacle is based on the set of known attributes for the obstacle.

6. The method of claim 1, further comprising the computer system receiving the target location from a user, wherein the computer system automatically navigates the vehicle to the target location in response to receiving the target location.

7. The method of claim 1, further comprising the computer system automatically identifying the target location based on a task being performed by the vehicle, wherein the computer system automatically navigates the vehicle to the target location in response to identifying the target location.

8. The method of claim 1, further comprising calculating an apparent extent of the obstacle using data corresponding to a location of the obstacle, wherein the determining a center of mass uses the apparent extent as the extent of the obstacle.

9. A system comprising:

a computer system to manage movement of a vehicle by performing a method comprising automatically navigating the vehicle from a current location to a target location, wherein the navigating includes;

selecting a set of linear paths for the vehicle to travel between the current location and the target location, the selecting including, for each linear path in the set of linear paths;

identifying a current linear path between the current location and the target location;

evaluating a set of cells along the current linear path for a presence of an obstacle;

instructing the vehicle to travel along the current linear path in response to evaluating all cells between the current location and the target location along the current linear path as not including an obstacle; and

in response to evaluating a cell in the set of cells as including an obstacle;

determining a center of mass corresponding to an extent of the obstacle;

identifying a set of potential locations based on the center of mass, a line through the center of mass and perpendicular to the current linear path, and the extent of the obstacle;

selecting a potential location in the set of potential locations as the intermediate location based on the extent of the obstacle and the current linear path; and

instructing the vehicle to travel along a distinct linear path from the current location to the intermediate location.

10. The system of claim 9, further comprising the vehicle, wherein the computer system is located on the vehicle.

11. The system of claim 9, wherein the selecting further includes, in response to evaluating a cell in the set of cells as including an obstacle, inflating the extent of the obstacle based on a size of the vehicle, wherein the determining a center of mass and the identifying a set of potential locations uses the inflated extent of the obstacle.

12. The system of claim 11, wherein the selecting further includes, in response to evaluating a cell in the set of cells as including an obstacle, calculating a cost for each of a plurality of potential locations in the set of potential locations, wherein the intermediate location corresponds to the potential location having a lowest cost.

13. The system of claim 9, the navigating further including obtaining data corresponding to a set of known attributes for the obstacle, wherein the extent of the obstacle is based on the set of known attributes for the obstacle.

14. The system of claim 9, further comprising the computer system receiving the target location from a user, wherein the computer system automatically navigates the vehicle to the target location in response to receiving the target location.

15. The system of claim 9, further comprising the computer system automatically identifying the target location based on a task being performed by the vehicle, wherein the computer system automatically navigates the vehicle to the target location in response to identifying the target location.

16. The system of claim 9, wherein the vehicle is operating in a rail yard, and wherein the target location corresponds to one of a plurality of waypoints throughout the rail yard, each waypoint corresponding to a location within the rail yard.

17. A computer program product comprising program code stored on at least one non-transitory computer-readable medium, which when executed, enables a computer system to implement a method of managing movement of a vehicle, the method comprising:

automatically navigating a vehicle from a current location to a target location, wherein the navigating includes;

selecting a set of linear paths for the vehicle to travel between the current location and the target location, the selecting including, for each linear path in the set of linear paths;

identifying a current linear path between the current location and the target location;

evaluating a set of cells along the current linear path for a presence of an obstacle;

instructing the vehicle to travel along the current linear path in response to evaluating all cells between the current location and the target location along the current linear path as not including an obstacle; and

in response to evaluating a cell in the set of cells as including an obstacle;

determining a center of mass corresponding to an extent of the obstacle;

identifying a set of potential locations based on the center of mass, a line through the center of mass and perpendicular to the current linear path, and the extent of the obstacle;

selecting a potential location in the set of potential locations as the intermediate location based on the extent of the obstacle and the current linear path; and

instructing the vehicle to travel along a distinct linear path from the current location to the intermediate location.

18. The computer program product of claim 17, wherein the selecting further includes, in response to evaluating a cell in the set of cells as including an obstacle, inflating the extent of the obstacle based on a size of the vehicle, wherein the determining a center of mass and the identifying a set of potential locations uses the inflated extent of the obstacle.

19. The computer program product of claim 18, wherein the selecting further includes, in response to evaluating a cell in the set of cells as including an obstacle, calculating a cost for each of a plurality of potential locations in the set of potential locations, wherein the intermediate location corresponds to the potential location having a lowest cost.

20. The computer program product of claim 17, further comprising the computer system receiving the target location from a user, wherein the computer system automatically navigates the vehicle to the target location in response to receiving the target location.

21. The computer program product of claim 17, further comprising the computer system automatically identifying the target location based on a task being performed by the vehicle, wherein the computer system automatically navigates the vehicle to the target location in response to identifying the target location.