SYSTEM FOR INTEGRATING DYNAMICALLY OBSERVED AND STATIC INFORMATION FOR ROUTE PLANNING IN A GRAPH BASED PLANNER

• US 20120046819A1
• Filed: 09/25/2008
• Published: 02/23/2012
• Est. Priority Date: 09/25/2008
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Agrawal, Mukul, Churchill, Daniel Chester
• Granted Patent: US 8,121,749 B1
• Time in Patent Office: Days
• US Class Current: 701/25
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Methods and systems of controlling an autonomous vehicle are provided. A method comprises controlling operations of the vehicle based at least in part on edge costs. An edge is a representation of a path the vehicle can traverse. Edge costs are determined by an estimation system and are based on at least one of an estimated travel time for an edge and a traverse-ability of the edge. The method further comprises sensing conditions of edges the vehicle is traversing and based on the sensed conditions, dynamically updating the edge costs.

Claims

1. A method of controlling an autonomous vehicle using a graph representing a plurality of routes the vehicle can travel, the graph comprising a plurality of vertices and a plurality of edges, wherein the vertices represent waypoints and each edge connects a respective two of the vertices, the method comprising:

controlling operations of the vehicle based at least in part on edge costs, wherein the edge costs are determined by an estimation system and are based on at least one of an estimated travel time for one of the plurality of edges and a traverse-ability of the edge;

sensing conditions of edges the vehicle is traversing; and

based on the sensed conditions, dynamically updating the edge costs for a current traversal from a starting point to a destination.

2. The method of claim 1, wherein controlling operations of the vehicle based at least in part on the edge costs, further comprises:

implementing a graph-based long term path planner, wherein the long term planner uses the edge costs to select from the plurality of edges a sequence of edges to traverse to reach the destination;

interpreting the sensed conditions along a traversed edge with a short term planner of the vehicle; and

informing the long term planner of the interpreted and sensed conditions with the short term planner.

3. The method of claim 1, further comprising:

adjusting the edge costs with the passage of time and in the absence of new sensed data for the edge.

4. The method of claim 1, further comprising:

updating the edge costs upon reaching a next expected waypoint in the current traversal from the starting point to the destination.

5. The method of claim 1, further comprising:

collecting data from static map information sources; and

collecting data obtained from dynamically-observed path information from the edges already travelled.

6. The method of claim 1, further comprising:

adjusting the edge costs to favor routes having redundancy, wherein the distance that the vehicle has to travel if an edge is blocked is reduced by using one of the redundant routes.

7. The method of claim 1, wherein the contributing factors to the edge costs include at least one of an estimated distance, existence of multiple paths, existence of multiple lanes, probability of blockage, existence of traffic lights, and a number of intersections.

8. The method of claim 1, further comprising:

determining if a path has a discontinuity; and

generating at least one soft waypoint at the discontinuity based on the determination of the discontinuity.

9. The method of claim 1, further comprising:

updating the edge costs associated with a traversed edge once the vehicle has traversed the edge.

10. A method of operating an autonomous vehicle using a graph representing a plurality of routes the vehicle can travel, the graph comprising a plurality of vertices and a plurality of edges, wherein the vertices represent waypoints, the method comprising:

implementing the graph describing an area to be traversed by the vehicle;

connecting the waypoints of the graph with traversable edges;

associating edge costs for each edge based at least in part on at least one of a distance of the edge, an estimated time to traverse the edge and traverse-ability of the edge;

based on the edge costs of the edges, planning a path to a destination through select edges at a graph-based long term path planner;

while traversing through the select edges, updating the edge costs at the graph-based long term path planner based on sensed information relating to conditions of the edges received from a short term planner; and

updating the path based on the updated edge costs at the graph-based long term path planner.

11. The method of claim 10, further comprising:

upon completion of the traversal of an edge, updating the an edge cost associated with the edge for future traversal estimates.

12. The method of claim 10, wherein the edge costs are further based at least in part on at least one of redundancy of paths connected to edge, whether the edge constitutes a sharp turn, an estimated probability of failure of traversal through the edge, limitation of road that makes up the edge, limitations of the vehicle, existence of multiple lanes, existence of traffic lights and number of intersections.

13. The method of claim 10, further comprising:

determining intersections.

14. The method of claim 10, further comprising:

applying Dijkstra'"'"'s algorithm to the edge costs in selecting a path of edges to traverse to the destination.

15. The method of claim 10, further comprising:

adjusting edge costs to favor routes having redundancy, wherein the distance that the vehicle has to travel if an edge is blocked is reduced by using one of the redundancy routes.

16. An autonomous vehicle, the vehicle comprising:

a vehicle controller configured to control operations of the vehicle using a graph representing a plurality of routes the vehicle can travel, the graph comprising a plurality of vertices and a plurality of edges, wherein the vertices represent waypoints and each edge connects a respective two of the vertices;

a long term planner configured to determine a path set out by waypoints to a destination, wherein the long term planner determines the path based on edge costs associated with the edges that connect the waypoints,

sensors configured to sense conditions associated with an edge while traversing the edge; and

a short term path planner configured to provide vehicle control directions to the vehicle controller using real-time processed sensor data from the sensors to a next waypoint in the path set out by the long term planner, the short term planner further configured to provide sensed condition signals based on the sensor data to the long term planner, wherein the long term planner is further configured to update edge costs based on the sensed condition signal.

17. The vehicle of claim 16, wherein the long term planner is configured to apply Dijkstra'"'"'s shortest path algorithm to the edge costs in determining a path.

18. The vehicle of claim 16, further comprising:

a memory to store the then current edge costs.

19. The vehicle of claim 16, wherein, the long term planner is further adapted to update edge costs once the vehicle has traversed the associated edge based on the sensed condition signals.

20. The vehicle of claim 16, wherein the long term planner is configured to avoid roadblocks in assigning edge costs by giving preference to at least one of longer routes and slower routes with multiple paths over those routes that are shorter and/or slower but with fewer alternative paths.