System and method of collision avoidance using intelligent navigation

• US 7,167,799 B1
• Filed: 03/23/2006
• Issued: 01/23/2007
• Est. Priority Date: 03/23/2006
• Status: Active Grant

• Current Assignee: Toyota Motor Corporation
• Original Assignee: Toyota Technical Center USA, Inc. (Toyota Motor Corporation)
• Inventors: Dolgov, Dmitri A., Laberteaux, Kenneth P.
• Primary Examiner(s): Camby; Richard M.
• Application Number:
  US11/387,414
• Time in Patent Office: 306 Days
• Field of Search: 701/36, 701/208, 701/211, 701/213, 701/216, 701/220, 701/300, 701/301, 342/357.06, 342/357.09, 342/357.14, 342/455
• US Class Current: 701/301
• CPC Class Codes: G08G 1/164 Centralised systems, e.g. external to vehicles

Abstract

A system and method of intelligent navigation with collision avoidance for a vehicle is provided. The system includes a global positioning system and a vehicle navigation means in communication with the global positioning system. The system also includes a centrally located processor in communication with the navigation means, and an information database associated with the controller, for identifying a location of a first vehicle and a second vehicle. The system further includes an alert means for transmitting an alert message to the vehicle operator regarding a collision with a second vehicle. The method includes the steps of determining a geographic location of a first vehicle and a second vehicle within an environment using the global positioning system on the first vehicle and the global positioning system on the second vehicle, and modeling a collision avoidance domain of the environment of the first vehicle as a discrete state space Markov Decision Process. The methodology scales down the model of the collision avoidance domain, and determines an optimal value function and control policy that solves the scaled down collision avoidance domain. The methodology extracts a basis function from the optimal value function, scales up the extracted basis function to represent the unscaled domain, and determines an approximate solution to the control policy by solving the rescaled domain using the scaled up basis function. The methodology further uses the solution to determine if the second vehicle may collide with the first vehicle and transmits a message to the user notification device.

Claims

1. A method of intelligent navigation with collision avoidance for a vehicle, said method comprising the steps of:

determining a geographic location of a first vehicle and a second vehicle within an environment using a navigation system, wherein the first vehicle and second vehicle are each in communication with a global positioning system to determine the geographic location of the first vehicle and second vehicle respectively;

modeling a collision avoidance domain of the environment of the first vehicle as a discrete state space Markov Decision Process using a centrally located processor in communication with the first vehicle;

scaling down the model of the collision avoidance domain;

determining an optimal value function and control policy that solves the scaled down collision avoidance domain, wherein the optimal value function is an approximate summation of a basis function that is dependent on domain variables;

extracting a representative basis function from the optimal value function;

scaling up the extracted basis function to represent the unscaled domain;

determining an approximate solution to the control policy by solving the rescaled domain using the scaled up basis function; and

using the solution to determine if the second vehicle may collide with the first vehicle, and transmitting an alert message to the first vehicle, if determined that the second vehicle may collide with the first vehicle.

2. A method as set forth in claim 1 further including the steps of:

sensing a location of the first vehicle using an input means in communication with the navigation system of the first vehicle.

3. A method as set forth in claim 1 wherein the alert message is transmitted via a user notification device.

4. A method as set forth in claim 1 wherein said step of modeling the environment as a Markov Decision Process further includes the steps of:

superimposing a grid on a map of the environment;

identifying a feature using the grid;

controlling the first vehicle using an agent, wherein the agent executes an action that stochastically controls the model of the collision avoidance domain, receives a reward from the environment and establishes a control policy for selecting actions that optimize the reward; and

defining a stochastic transition model of a probabilistic behavior of the second vehicle.

5. A method as set forth in claim 4 wherein the reward is positive for no collision between the first vehicle and second vehicle and the reward is negative for a collision between the first vehicle and second vehicle.

6. A method as set forth in claim 1 wherein said step of scaling down the model of the collision avoidance domain further includes the step of reducing the size of the grid.

7. A method as set forth in claim 1 wherein said step of extracting a basis function further includes the steps of extracting a primal basis function and a dual basis function that provide a predetermined control policy for the collision avoidance domain.

8. A method as set forth in claim 7 wherein the optimal value function is an inverse of a relative distance between the first vehicle and the second vehicle.

9. The method as set forth in claim 1 wherein said step of scaling the basis function up further includes the steps of:

modeling a set of smaller Markov Decision Process using pairs of objects.

10. A method of intelligent navigation with collision avoidance for a vehicle, said method comprising the steps of:

sensing a location of a first vehicle using an input means in communication with a navigation system on the first vehicle, wherein the first vehicle navigation system is in communication with a global positioning system;

sensing a location of a second vehicle using an input means in communication with a navigation system on the second vehicle, wherein the second vehicle navigation system is in communication with the global positioning system;

determining a geographic location of the first vehicle and the second vehicle within an environment using the sensed location of the first vehicle and the sensed location of the second vehicle by a centrally located processor in communication with the first vehicle navigation system and second vehicle navigation system;

modeling a collision avoidance domain of the environment of the first vehicle as a discrete state space Markov Decision Process by superimposing a grid on a map of the environment, identifying a feature using the grid, and controlling the first vehicle using an agent, wherein the agent executes an action that stochastically controls the model of the collision avoidance domain, receives a reward from the environment and establishes a control policy for selecting actions that optimize the reward and defines a stochastic transition model of a probabilistic behavior of the second vehicle;

scaling down the model of the collision avoidance domain;

determining an optimal value function and control policy that solves the scaled down collision avoidance domain, wherein the optimal value function is an approximate summation of a basis function that is dependent on domain variables;

extracting a representative basis function from the optimal value function;

scaling up the extracted basis function to represent the unscaled domain;

determining an approximate solution to the control policy by solving the rescaled domain using the scaled up basis function; and

using the solution to determine if the second vehicle may collide with the first vehicle, and transmitting an alert message to the first vehicle, if determined that the second vehicle may collide with the first vehicle.

11. A method as set forth in claim 10 wherein the alert message is transmitted via a user notification device.

12. A method as set forth in claim 10 wherein the reward is positive for no collision between the first vehicle and second vehicle and the reward is negative for a collision between the first vehicle and second vehicle.

13. A method as set forth in claim 10 wherein said step of scaling down the model of the collision avoidance domain further includes the step of reducing the size of the grid.

14. A method as set forth in claim 10 wherein said step of extracting a basis function further includes the steps of extracting a primal basis function and a dual basis function that provide a predetermined control policy for the collision avoidance domain.

15. A method as set forth in claim 10 wherein the optimal value is an inverse of a relative distance between the first vehicle and the second vehicle.

16. The method as set forth in claim 10 wherein said step of scaling the basis function up further includes the steps of:

modeling a set of smaller Markov Decision Process using pairs of objects.

17. An intelligent navigation system with collision avoidance for a vehicle comprising:

a global positioning system which includes a global positioning transceiver associated with a first vehicle, a global positioning transceiver associated with a second vehicle, and a global positioning signal transmitter in communication with the first vehicle global positioning transceiver and second vehicle global positioning transceiver;

a navigation means on a first vehicle in communication with the global positioning system;

a centrally located processor in communication with said navigation means on said first vehicle and the navigation means on said second vehicle;

an information database associated with the controller for identifying a location of said first vehicle;

an input means on the first vehicle for sensing a location of the first vehicle, and said input means is in communication with said first vehicle navigation means;

an alert means for providing an alert message to an operator of the first vehicle regarding a collision with the second vehicle, wherein the alert means is operatively in communication with said centrally located processor; and

wherein the centrally located processor hosts an intelligent navigation computer software program that uses the geographic location of the first vehicle and the geographic location of the second vehicle within the environment to model a collision avoidance domain of the environment of the first vehicle as a discrete state space Markov Decision Process, by scaling down the model of the collision avoidance domain, determining an optimal value function and control policy that solves the scaled down collision avoidance domain, wherein the optimal value function is an approximate summation of a basis function that is dependent on domain variables, extracts a representative basis function from the optimal value function, scales up the extracted basis function to represent the unscaled domain, determines an approximate solution to the control policy by solving the rescaled domain using the scaled up basis function, and uses the solution to determine if the second vehicle will collide with the first vehicle, and provides an alert message to the first vehicle, if determined that the second vehicle may collide with the first vehicle.