A proposal for our application to the INTAS project (Year of 2004-2005)

A Design of Intelligent and Autonomous Public Transportation System by Co-evolution

Akira Imada (Brest State Technical University)

This version was last modified on

April 30, 2010

Abstract

Nowadays every big city has its own public transportation system, like the one with citybuses as we can see everywhere all over the world. This article describes a design of such system. Usually, public vehicles follow the pre-set courses with a pre-set schedule determined by human. Our goal is to make each of these vehicles determine autonomously and intelligently by themselves their appropriate behavior such as, what time should it start; which course should it follow; how long should it stay at one stop, and so on. The design will be by co-evolution between the system of transportation versus traffic environment. The latter includes three items: (i) a map of roads which is created randomly at the start; (ii) not-so-intelligent-but-rather-with-random-movement people, like us; and (iii) cars with not so intelligent behavior either. The transportation system evolves to be more and more intelligent while environment evolves to be more and more difficult to be explored.

keywords: autonomous-intelligent-public-vehicle, road-map-of-evolving-complexity, co-evolution, neural-networks, finite-automaton, multi-agent-system, evolutionary-computations, artificialimmune-system, artificial-ants, swarm-intelligence

1 Introduction

One late autumn day in the year of 2003, at a conference held in Minsk, Kurosh Madani from Paris addressed a question to us.

Assume we have two alternatives to fly from Paris to Tokyo: one with human pilot, the other by a totally autonomous navigation system with no human pilot at all. Which would you prefer to choose?

I want a monkey with a uniform like a pilot in the cockpit who pretends to navigate the jet in order for the flight to look safe. Still, however, I would rather choose a human pilot at this current stage of development of auto aviation system. Subconscious part of mind would tell me it’s too risky to choose an auto pilot system even with a reliable looking monkey pilot. The jet without pilot, however, is not so difficult technology these days. As a matter of fact, air force in certain countries employs such system for military purpose practically enough. This article is to tackle probably a more challenging task than a jet-auto-navigation-system, that is, to design a public transportation system in a fairly big town.

Recently I read an article in New York Times which wrote:

The private bus service has long been criticized by its customers, by rider advocacy groups, and even by city officials ... as being shoddy and sporadic ... But officials at the authority, which currently runs 4,500 city buses and is the largest bus system in the country, insist that it is fully prepared to take over the lines, and that improvements will be noticed quickly. Tom Kelly, an authority spokesman, said that the takeover was ”a challenge we’re looking forward to” and that the authority was already studying the private routes in detail. The authority hopes to make the bus routes more efficient, he said, possibly by consolidating some routes that are near one another ... The transition will be a challenge, but in a year from now I think service will be better,” he said. ”The M.T.A. runs better service on their lines than the private lines.” — from New York Times, 26 April 2004.

Public transportation problem is already quite an established field, as Pursula [1] wrote:

During its more than forty years long history computer simulation in traffic analysis has developed from a research tool of limited group of experts to a widely used technology in the research, planning, demonstration and development of traffic systems ... Road transportation, that is, efficient movement of people and goods through physical road and street networks is a fascinating problem. Traffic systems are characterized by a number of features that make them hard to analyze, control and optimize. The systems often cover wide physical areas, the number of active participants is high, the goals and objectives of the participants are not necessarily parallel with each other or with those of the system operator (system optimum vs. user optimum), and there are many system inputs that are outside the control of the operator and the participants (the weather conditions, the number of users, etc.). In addition, road and street transportation systems are inherently dynamic in nature, that is, the number of units in the system varies according to the time, and with a considerable amount of randomness. The great number of active participants at present at the same time in the system means a great number of simultaneous interactions.

Sorry for such a long quotation, but how this description is similar to, and thus, well motivates our initially spontaneous idea of evolving a public transportation system! Then what is new of our plan? It is the concept of Co-evolution to elaborate the traffic system, which is innovative idea as far as I know, (limited knowledge, I might add, though.) The co-evolution is between the transportation system and the geography of the town. Both evolve gradually from a simple one to a complex one, with competing each other.

Furthermore, behaviors of public-vehicles, humans, and other cars will be by either of Neural Network, Finite Automaton, or whatever else, as three independent Multi Agent Systems, which is, whatever the combination might be, quite a standard approach these days, though. The town also could have an Anomaly Detecting System such as traffic jams, accidents, ... etc, and it will be constructed by Artificial Immune System, Artificial Ant System, Swarm Intelligent Particles, or something like that.

In the following section, each of these concepts is described a little more in detail.

2 Methods

2.1 Co-evolution

In 1991, in the conference called ALIFE-II the proceeding of which contains a full of ideas of even now still very interesting, Hillis [2] showed us a very elegant evolution of a sorting network whose goal was to sort out 32 items efficiently, that is, with as few comparisons as possible. He employed a co-evolution between sorting network versus a set of 32 items to be fed to the sorting network. Result suggested that as 32 items evolves to be more and more difficult to be sorted out, while sorting network evolves to be more and more efficient and eventually the network sort any set of 32 items with 60 comparisons and still we have not known more efficient sorting network.

Since then, this concept of co-evolution has become familiar also in Evolutionary Robotics (see, e.g. Bullock [3] which also gives us not only an excellent survey on co-evolution but discussed it as a computational design technique for evolutionary robotics.)^{1} .

In our project, the co-evolution will be intended as multiple bus-like-public-vehicle not intelligent at the beginning versus fictitious road map starting with very simple geography. The road map evolves to be more and more difficult to be controlled and The transportation system, on the other hand, evolves to be more and more effective, efficient, and safe.

2.2 How the autonomous vehicle will be driven?

Then the first question is, in what way those intelligent autonomous vehicles can be driven? The general concept is that a vehicle is taken as an agent and a population of agents evolves in a given environment over many generations and the some of best agents survive. As such agents we have some alternatives as follows:

Neural-Networks: When we try to simulate a vehicle, what hits my mind instantaneously is to employ a feed-forward neural networks (NNs) with sensor input from the environment and motor outputs to control its wheels to move forward, backward turn right or left and so on. In such a dynamic environment, it is an artificial evolution that we could employ effectively when we train the neural network, not only its weight but also its architecture if necessary. See Ruppin [4] for example.

1 The term Co-evolution was originally coined by P. R. Ehrlich and P. H. Raven (1964) in their paper “Butterflies and plants: a study in coevolution.” Evolution 18, 586-608, in which authors discuss butterflies and plants interaction as host-enemy co-evolution, though the concept had been appeared before such as in V. G. Dethier (1954) “Evolution of Feeding Preferences in Phytophagous insects. Evolution 8, pp 33-54. However, in the context of computational co-evolution, in addition to the Hillis’s paper above, D. H. Janzen’s (1980) “When is it coevolution?” Evolution 34, pp. 611-612, is often cited as a landmark because of his redefinition of Ehrlich and Raven’s co-evolution. All of these three papers are from an aspect of biological evolution. Then Bullock above discussed co-evolution as a computational design technique.

Finite-Automaton: What attracts me more to employ for the purpose is a finite-state automaton (FAM). When we evolve FAM aiming to make it some tasks, starting with a very simple structure, it will be very impressive to observe the way it evolves to grow into very sophisticated structures and, as a result, very elaborate behaviors. In the above mentioned proceedings of ALIFE-II conference, we can see many such examples. The most I was impressed was the one by MacLennan [5] in which he created, not a moving objects but, objects who communicate with each other intelligently, Thus we might assume that when we say evolving FAM, it implies evolving its structure, while evolution of NNs, we have to design chromosomes in somewhat of a tricky way (see for example Stanley et al. [6].)

Artificial Immune System: Lei Wang at al. [7], for example, controlled Khepera robot with 8 infra-red sensors and 2 wheels under Braitenberg’s model [8] with employing Artificial Immune System (AIS) and concluded that if environment changes dynamically from time to time and effects strongly on the robot’s behavior, AIS is theoretically better than the ordinary evolutionary algorithms on the learning capability from its experiences partly because degeneration issue could be eliminated more quickly than GA since AIS has the function of long-term memory while GA usually can only remember the gene information from its patent generation. We can see yet another example of controlling its walking of mobile robot by AIS in Ishiguro [9].

Artificial Ant Algorithm: Ant algorithms proposed by Dorigo [10] could also be employed to optimize the courses of our public vehicles, since it was originary inspired by the observation of real ant colony’s foraging behavior of how ants can find shortest paths between food sources and their nest. See Di Carlo and Dorigo [11] for an adaptive multi-agent routing algorithm inspired by ants behavior. However, I doubt it will not be so easy to control our vehicles by this Artificial Ant Colony Algorithm in real-time, if not impossible.

What else? Instead of employing those already explored technique mentioned above, it is also a part of our project to find quite innovative methods of controlling our public vehicles.

2.3 What about other cars and human movement?

Then what about other cars and passengers/pedestrians moving around everywhere on the road-map? Behavior of other cars and human should be not so intelligent, like us, in order for the simulation to be more realistic.

Analysis of the Behaviors of drivers have been reported fairly a lot: Unsal [12] proposed three different human driver models which were designed for an automated highway-vehicle systems (AHS); Brackstone et al. [13] models driver behavior in their Intelligent Transport Systems (ITS); Al-Kaisy et al. [14] evaluated ITS strategies by simulating lane changing rules of drivers at freeways.

As for pedestrian, D Helbing [17] modeled a pedestrian dynamics. ^{2}

2 In their paper, authors give us also an excellent survey of what they call a history of modeling approaches to pedestrian dynamics. Here, let me pick up two of them: (1) Borgers and Timmermans developed a model for the route choice behavior of pedestrians according to demands, current locations and store location A. Borgers

2.4 Evolution of Road-map

microsimulation of self-organization phenomena occuring in traffic systems including formation of jammed states in freeway or city traffic as well as the various collective patterns of motion developing in pedestrian crowds like oscillatory changes of the walking direction at narrow passages or round-about traffic at crossings.

The authors posed us a question of whether there is a common underlying dynamics which allows for a generalized description of the formation and evolution of trail systems. As they went on to say, trails are adapted to the requirements of their users. Frequently used trails become more developed, making them more attractive, wehreas rarely used trails vanish again. Trails with large detours become optimized by creating shortcuts. New destinations or entry points are connected to an existing trail system. These dynamical processes occur basically without any common planning or direct communication among the users. Instead, the adaptation process can be understood as a self-organization phenomenon, resulting from the non-linear feedback between the users and the trails. Then they proposed a particle-based, multi-agent approach to structure formation using the class of active walkers which subject to fluctuations and influences of their environment while also the walkers change their environment locally, which in turn influences their further movement and their behavior, in particular changes produced by some walkers can influence other walkers. Hence, the non-linear feedback can be interpreted as an indirect interaction between the active walkers via environmental changes, which may lead to the selforganization of of spatial structures. Finally, in the last section an application of the model to the optimization of trail systems is suggested.

Wow! How fascinating! This could be almost perfect tool for our public vehicle, not walker though, to co-evolve to form the complicated trail in the town and elegant system of transportation.

2.5 Anomaly detection

Dasgupta [15], for example, designed a multi agent system for intrusion and/or anomaly detection in a computer network using reinforcement learning of Artificial Immune System (AIS) to sense its dynamic environment, to detect and eliminate pathogens and to memorize them for future recognition. AIS has its ability to adapt to continuously changing environments, dynamically learning the fluid patterns of ’self’ and predicting new patterns of ’non-self’. Why don’t we apply this to our public transportation system? In fact Dasgupta wrote:

A real environment produces new network traffic continuously in real time. Thus antigens faced by the AIS will be different every day. More importantly, normal behaviors of network traffic on one day, which are considered as self antigens, can be different from normal behaviors of network traffic on another day. Therefore, the AIS needs to be extended, firstly to learn normal behaviors by undergoing only a small subset of self antigens at one time. Secondly its detectors should be replaced whenever previously observed normal behaviors no longer represent current normal behaviors.

and H.J.P. Timmermans (1986) “City center entry points store location patterns and pedestrian route choice behavior: A microlevel simulation model.” Socio-Economic Planning Science 20, pp 25–31.

(2) Henderson suggested pedestrian crowds can be described by the Navier-Stokes equations of fluid-dynamics, in L.F.Henderson “On the fluid mechanics of human crowd motion.” Transportation Research 8, 509–515 (1974)

(3) Furthermore A fluid dynamic pedestrian model uses the basis of a pedestrian specific Boltzmann-like gas-kinetic model D. Helbing (1992) A fluid-dynamic model for the movement of pedestrians Complex systems 6, 391–415.

How interesting! If we removed “network” from the above quotation, it would look like a description of our public transportation system, would it not? He went on to write

⋯ extended AIS creates new detectors every day after the system experiences new network traffic which has not been presented before.

2.6 A measure of complexity of a road-map

In order to co-evolve, we need to know how the road-map started with a very simple one evolve it’s complexity. Hence the project should include a proposition of mathematically valid measure of complexity of the road-map. This would be a fitness function on the part of road-map.

3 What could be of our interest?

What have described so far is the first stage of the project. Then observation we might be interested in would be as follows.

3.1 Discrepancy between in-screen and on-tabletop

Discrepancy between real simulations and the ones in PC; Why and how much is the difference will be one of our important topics. Since simulations on a real table-top would be under very limited resources due to some physical and/or financial reasons, simulations on PC screens would be usually more preferable. However it will be more likely to have different results from a real one.

3.2 Generalization

Could we make the vehicles to have a capability of generalization, that is, after learning to be intelligent they still could keep the intelligence in a different environment?

3.3 To know what-could-be rather than what-have-been.

This is like once very popular phrase used by C. Langton in Artificial Life community (See his preface in the above several mentioned proceedings of ALIFE II.) Such simulation as in this article is also interesting from different aspect like Civil Engineering point of view, and in order for us to create a real innovative system, sometimes it is important to forget what-have-been but enjoy what-could-be.

4 A Toy Implementation

First, we have to design how we make one public transportation vehicle move with, say, simplest FAM of two states, one sensor input, and two motor output. Second, we design a few passengers, pedestrians, and cars whose behaviors are quasi-random but at least follow, not perfectly though, a traffic rule which is determined by us in advance. Each of these not so intelligent objects moves also by a simplest FAM. Fourth, these four different types objects are put also on a very simple environment as shown in Figure 1.

Figure 1: An example of road-map to start evolution with.

Then, all of them start evolution with the goal of increasing their own fitness value. The fitness evaluation of evolving road-map is to decrease the fitness of the public vehicle.

5 Summary

In short, though not so short actually, our candidate sub-topics during the project are as follow.

• How to design of public vehicle, passenger, and car.

• How to evolve road system.

• How to evaluate the complexity of road system.

• How to co-evolve traffic system with road system

• Simulation in real environment.

• Consideration on why is simulation in-screen could be different than on-real-desktop?

• Consideration on how could be applied our results to a real world traffic system.

Each team in our international collabolation chooses one or two topics from the above list, and develop the project independently but communicating with each other via Internet from time to time.

Even if the proposal are not accepted unfortunately, we could proceed the project with the scale being a little down-sized. Why not? We have some high quality international conferences on line these days — no fee for registration, transportation, nor accommodation are needed; we have Internet to communicate. In any case, let’s start the project now with the goal being, say, to publish our results in one of the highest quality international journal.

no more clever-looking pilot monkey.

6 Acknowledgment

I thank my colleague Vladimir Golovko in Brest. The very first idea of this thought flashed through my mind during I talked with him about our future project. Thanks also go to Rauf Sadykhov in Minsk for his always innocent encouragement.

References

[1] M. Pursula (1999) Simulation of Traffic Systems — An Overview. Journal of Geographic Information and Decision Analysis, Vol.3, No.1, pp,1–8.

[2] W. D. Hillis (1991) Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure. Artificial Life II. Santa Fe Institute Studies in the Science of Complexity, Vol. X, Addison-Wesley.

[3] S. G. Bullock (1995) Co-evolutionary Design: Implications for Evolutionary Robotics In proceedings of the 3rd European Conference on Artificial Life.

[4] E. Ruppin (2001) Evolutionary Autonomous Agents: A neuroscience Perspective.

[5] B. MacLennan (1991) Synthetic Ethology: An Approach to the Study of Communication. Artificial Life II. Santa Fe Institute Studies in the Science of Complexity, Vol. X, Addison-Wesley.

[6] K. O. Stanley and R. Miikkulainen (2001) Evolving Neural Networks through Augmenting Topologies. The University of Texas at Austin, Technical Report TR-AI-01-290.

[7] L. Wang at al. (2003) An Evolutionary Algorithm with Population Immunity and its Application on Autonomous Robot Control. In Proceedings of the IEEE congress on Evolutionary Computation.

[8] V. Braitenberg (2000) Vehicles: Experiments in Synthetic Psychology MIT Press.

[9] K. Ishiguro (1997) Emergent Construction of Artificial Immune Networks for Autonomous Mobile Robots. In Proceedings 1997 IEEE International Conference on System Man and cybernetics.

[10] M. Dorigo (1992) Optimization, Learning and Natural Algorithms. (in Italian) Ph.D. thesis. Dipartimento di Elettronica e Informazione, Politecnico di Milano.

[11] G. Di Caro and M. Dorigo (1998) An Adaptive Multi-agent Routing Algorithm Inspired by Ants Behavior. In Proceedings of 5th Annual Australasian Conference on Parallel and Real-Time Systems.

[12] C. Unsal (1998) Human Driver Models for AHS simulation Carnegie Mellon University: Robotic Institute Technical Report CMU-RI-TR-98-02.

[13] M. Brackstone et al. (2003) Driver Behavior and Traffic Modeling: Are we looking at the Right Issues? In Proceedings of IEEE Intelligent Vehicles Symposium

[14] A. F. Al-Kaisy, J. A. Stewart, and M. Van Aerde (1999) Microscopic Simulation of Lane Changing Behavior at Freeway Weaving Sections. Canadian Journal of Civil Engineering, 26(6), 840-851.

[15] D. Dasgupta and F. Gonzalez (2002) An Immunity-Based Technique to Characterize Intrusions in Computer Networks. IEEE Transactions on Evolutionary Computation, 6(3).

[16] J. Kim and P. J. Bentley Towards and Artificial Immune System for Network Intrusion Detection: An Investigation of Dynamic Clonal Selection.

[17] D. Helbing, P. Molnar, F. Schweitzer (1994) Computer simulations of Pedestrian Dynamics and Trail Formation. Journal of Evolution of Natural Structures 229–234.

[18] D. Helbing, F. Schweitzer, J. Keltsch, and P. Molnar (1997) Active Walker Model for the Formation of Human and Animal Trail Systems. Physical Review E 56, pp 2527-2539,