Method and apparatus for model-free optimal signal timing for system-wide traffic control

• US 5,668,717 A
• Filed: 10/12/1995
• Issued: 09/16/1997
• Est. Priority Date: 06/04/1993
• Status: Expired due to Term

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Spall, James C.
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US08/545,049
• Time in Patent Office: 705 Days
• Field of Search: 364/148, 364/147-151, 364/157, 364/158, 364/164, 364/165, 364/436-438, 395/21-23, 395/904, 395/905, 395/912, 395/913, 395/919, 395/906
• US Class Current: 700/51
• CPC Class Codes: G08G 1/081 Plural intersections under common control

Abstract

A method and apparatus for model-free, real-time, system-wide signal timing for a complex road network is provided. It provides timings in response to instantaneous flow conditions while accounting for the inherent stochastic variations in traffic flow through the use of a simultaneous perturbation stochastic approximation (SPSA) algorithm. This is achieved by setting up several (M) parallel neural networks, each of which produces optimal controls (signal timings) for any time instant (within one of the M time periods) based on observed traffic conditions. The SPSA optimization technique is critical to the feasibility of the approach since it provides the values of weight parameters in each of the neural networks without the need for a model of the traffic flow dynamics.

Claims

1. A method for managing a complex transportation system, wherein a model governing the system dynamics and measurement process is unknown, to achieve optimal traffic flow by automatically adapting to both daily non-recurring events and to long-term changes in the system by approximating a controller for the system without having to first build the model therefor and without having, thereafter, to periodically and manually recalibrate the model, the method comprising the steps of:

using a plurality of sensors to obtain traffic flow information about the system;

inputting the traffic flow information into a data processing means;

approximating the controller using the data processing means and the traffic flow information comprising the steps of;

selecting a single function approximator to directly approximate the controller;

estimating the unknown parameters of the single function approximator in the controller using a stochastic approximation algorithm that does not require the model for the system; and

using the single function approximator to approximate the controller, wherein the controller is an output of the single function approximator; and

using the controller to control traffic control means to achieve optimal traffic flow.

2. The method as recited in claim 1, the selecting a single function approximator step comprising the step of selecting a single continuous function approximator to directly approximate the controller.

3. The method as recited in claim 1, the estimating the unknown parameters step comprising the step of estimating the unknown parameters of the single function approximator in the controller using a simultaneous perturbation stochastic approximation algorithm.

4. The method as recited in claim 3, the selecting a single function approximator step comprising the step of selecting a neural network to directly approximate the controller.

5. The method as recited in claim 4, the selecting a neural network step comprising the step of selecting a multilayered, feed-forward neural network to directly approximate the controller.

6. The method as recited in claim 4, the selecting a neural network step comprising the step of selecting a recurrent neural network to directly approximate the controller.

7. The method as recited in claim 3, the selecting a single function approximator step comprising the step of selecting a polynomial to directly approximate the controller.

8. The method as recited in claim 3, the selecting a single function approximator step comprising the step of selecting a spline to directly approximate the controller.

9. The method as recited in claim 3, the selecting a single function approximator step comprising the step of selecting a trigonometric series to directly approximate the controller.

10. The method as recited in claim 3, the selecting a single function approximator step comprising the step of selecting a radial basis function to directly approximate the controller.

21. The method as recited in claim 1, further comprising, after the selecting a single function approximator step, the step of choosing an initial set of values for the unknown parameters of the single function approximator.

22. The method as recited in claim 21, wherein the initial set of values is derived from historical data.

23. The method as recited in claim 21, wherein the initial set of values is derived from a simulation.

24. The method as recited in claim 21, wherein the initial set of values is the set of values that causes the single function approximator to produce a reasonable output.

25. The method as recited in claim 1, wherein data input to the stochastic approximation algorithm comprises data from a time period less than or equal to twenty-four hours.

26. The method as recited in claim 25, wherein data input to the stochastic approximation algorithm comprises data from the same time period on two or more days.

11. A computerized management system for achieving optimal traffic flow in a complex transportation system, wherein a model governing the transportation system dynamics and measurement process is unknown, by automatically adapting to both daily non-recurring events and to long-term changes in the transportation system by approximating a controller for the transportation system without having to first build the model therefor and without having, thereafter, to periodically and manually recalibrate the model, the management system comprising:

a plurality of sensors for obtaining traffic flow information about the transportation system;

a data processing means for receiving the traffic flow information;

means for approximating the controller using the data processing means and the traffic flow information, the approximating the controller means comprising;

a single function approximator to directly approximate the controller;

means for estimating the unknown parameters of the single function approximator in the controller using a stochastic approximation algorithm that does not require the model for the system; and

means for using the single function approximator to approximate the controller, wherein the controller is an output of the single function approximator; and

traffic control means using the controller to achieve optimal traffic flow.

12. The system as recited in claim 11, wherein the single function approximator comprises a single continuous function approximator to directly approximate the controller.

13. The system as recited in claim 11, the means for estimating the unknown parameters of the single function approximator in the controller comprising a simultaneous perturbation stochastic approximation algorithm.

14. The system as recited in claim 13, wherein the single function approximator comprises a neural network to directly approximate the controller.

15. The system as recited in claim 14, wherein the neural network comprises a multilayered, feed-forward neural network to directly approximate the controller.

16. The system as recited in claim 14, wherein the neural network comprises a recurrent neural network to directly approximate the controller.

17. The system as recited in claim 13, wherein the single function approximator comprises a polynomial to directly approximate the controller.

18. The system as recited in claim 13, wherein the single function approximator comprises a spline to directly approximate the controller.

19. The system as recited in claim 13, wherein the single function approximator comprises a trigonometric series to directly approximate the controller.

20. The system as recited in claim 13, wherein the single function approximator comprises a radial basis function to directly approximate the controller.

27. The system as recited in claim 11, further comprising an initial set of values for the unknown parameters of the single function approximator.

28. The system as recited in claim 27, wherein the initial set of values is derived from historical data.

29. The system as recited in claim 27, wherein the initial set of values is derived from a simulation.

30. The system as recited in claim 27, wherein the initial set of values is the set of values that causes the single function approximator to produce a reasonable output.

31. The system as recited in claim 11, wherein data input to the stochastic approximation algorithm comprises data from a time period less than or equal to twenty-four hours.

32. The system as recited in claim 31, wherein data input to the stochastic approximation algorithm comprises data from the same time period on two or more days.