Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Traffic analysis or control of surface vehicle
Reexamination Certificate
2001-01-16
2002-10-22
Beaulieu, Yonel (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Traffic analysis or control of surface vehicle
C701S301000, C340S901000, C340S905000, C340S425500, C706S013000, C706S015000
Reexamination Certificate
active
06470261
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to artificial neural networks and, more specifically, to an implementation of an automatic freeway incident detection system using artificial neural networks and genetic algorithms.
BACKGROUND OF THE INVENTION
In the management of traffic on a freeway, much effort has been concentrated on improving traffic safety and efficiency by improving use of the existing road network through homogenized traffic flow and avoidance of critical situations for the individual driver. Unexpected disturbances in the existing road network are usually caused by incidents such as traffic delays, accidents, disabled vehicles, spilled loads, maintenance, and other events that disrupt the normal flow of traffic. This results in a reduction of the capacity of the road network. “Incidents” are defined as non-recurring events that deteriorate road safety conditions. In order for a traffic management system to be effective, it must be capable of detecting unexpected disturbances, for example, through use of an automated incident detection systems, in a manner that is both reliable and quick to respond.
Automated incident detection systems have typically included two major components, which are a traffic detection system and an incident detection algorithm. The traffic detection system, which is part of the traffic management scheme, acquires current traffic data. The incident detection algorithm interprets the data acquired by the traffic detection system and ascertains the presence or absence of incidents or non-recurring congestion. Usually, the detection of traffic incidents is based on observing specific discontinuities in the traffic data and the incident detection algorithm is highly dependent on the traffic detection system. Accordingly, the accurate and quick detection of the occurrence and location of unexpected traffic flow disturbances is vital for traffic surveillance, as is the design of neural networks used in detection algorithms for interpreting the detected traffic data. In particular, improvements in these areas are continually being sought so that motorists may be informed by real-time traveler information services employing this technology to allow for alternate routing of traffic and timely dispatch of emergency services.
A number of incident detection algorithms had been proposed from a variety of theoretical foundations over last two decades. They range from comparative or pattern comparison algorithms to the artificial intelligent type. However, their structures vary in different degree of sophistication, complexity and data requirements. The existing algorithms such as California, MacMaster and Minnesota Algorithms are classified as comparative methods and they have some design uncertainties and difficulties, especially in deciding threshold values when there is a lack of heuristic knowledge. The artificial intelligence type neural network proposals have been shown to be a promising approach but these types suffer from being mostly manually designed in an ad-hoc manner.
Therefore, what is needed is an automatic freeway incident detection system that incorporates improved neural network design capabilities in the incident detection software for more efficient and accurate detection of freeway incidents.
SUMMARY OF THE INVENTION
The present invention relates to the design of a neural network (“NN”) for automatic detection of incidents on a freeway. A NN is trained using a combination of both back-propagation and genetic algorithm-based methods. The back-propagation and genetic algorithm work together in a collaborative manner in the NN design. A gradient-guided back-propagation method employs a fast leaning technique that utilizes both incremental and batch learning techniques. The training starts with incremental learning based on the instantaneous error and the global total error is accumulated for batch updating at the end of training data being presented to the NN. The genetic algorithm directly evaluates the performance of multiples sets of NNs in parallel and then uses the analyzed results to breed new NNs that tend to be better suited to the problems at hand. Both global and local search capabilities are enhanced in this hybrid system, in which back-propagation training provides the local search and the genetic algorithm explores the global. Such a systematic and reusable artificial intelligence computing paradigm focuses on design automation.
In one embodiment, the presence or absence of incidents of traffic congestion at selected time instances are identified by first acquiring and storing traffic data. At least one neural network is used for evaluating the traffic data to determine the incident status for a particular time instance. The neural network is updated utilizing both back propagation and genetic algorithm techniques for optimizing the design of the neural network.
In another aspect, traffic data is stored in a data server and simulated traffic data is generated therefrom with pre-defined incident occurrences, such that the simulated traffic data is used as input in optimizing the design of the updated neural network.
The traffic data used can be formatted as rows of data set instances that include incident status, traffic volume at time instances collected at an upstream traffic measurement station, occupancy at time instances collected at an upstream traffic measurement station, traffic volume at time instances collected at a downstream measurement location, and occupancy at time instances collected at a downstream traffic measurement location.
Updating the neural network can be accomplished by first generating an initial population of neural network design candidates encoded in chromosomes, each candidate being assigned with a fitness value obtained from evaluation of performance. The initial neural network design candidates are ranked from best to worst and a global record is maintained of the best fitness neural network design candidate. Mating population selection operations are performed, followed by crossover and mutation operations on the selected neural network design candidates to generate a new population of neural network design candidates, so that a global search has been executed via the rank-based selection, crossover and mutation operations. A back propagation training operation is then performed on the neural network design candidates, so that a local search has been executed and weights of the neural network's connections are modified to generate a new population of neural network design candidates. The fitness of the back-propagated neural network design candidates are evaluated and a fitness value is assigned thereto. Then a generation gap operation is performed that selects candidates from the new population and previous populations of neural network design candidates that will survive into the next evolution. The evolution process of genetic reproduction is repeated until a stop criterion is reached.
A technical advantage achieved with the invention is the reduction of the design time of NNs compared to the traditional neural-genetic design means, the latter of which are lacking in diversified exploring capabilities. Another advantage is the ability to handle longer chromosome lengths by virtue of being equipped with the neighborhood search capability using a gradient-guided local search technique, which derives naturally from the traditional training, i.e. the back-propagation training. This ameliorates the typical circumstance that as the chromosome length increases, the search space will increase exponentially leading to a longer search time or failure to reach a near-optimal solution.
Another technical advantage achieved with the invention is that the use of real number coding avoids “Hamming Cliffs” problems normally associated with the binary coding commonly used in the traditional neural-genetic design means. Flexibility is also derived from the real number coding for its multi-modal coding capability to handle integer, symbolic and real value representations. Therefore in
Ng Kim Chwee
Ng Yew Liam
Beaulieu Yonel
CET Technologies PTE LTD
Haynes and Boone LLP
LandOfFree
Automatic freeway incident detection system and method using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic freeway incident detection system and method using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic freeway incident detection system and method using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2933704