\documentstyle[12pt,eclepsf]{article}
\textheight 240mm
\topmargin -10mm
\textwidth 170mm
\oddsidemargin -7mm

\markright{(For INTAS Application)}

\begin{document}
\title{{\small A proposal for our application to the INTAS project (Year of 2004-2005)}
\hspace*{1in}\\
A Design of Intelligent and Autonomous Public Transportation 
System by Co-evolution 
%%with randomly created maps of roads
%%where not-so-intelligent-but-rather-random people (like us) 
%%and cars being on the map
}
\author{Akira Imada\\
(Brest State Technical University) \\
      \hspace*{1in}\\
        {\small This version was last modified on}}
\maketitle

\begin{abstract}
\noindent
Nowadays every big city has its own public transportation system,
like the one with city-buses 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.
\end{abstract}

\noindent
{\bf keywords:} {\it autonomous-intelligent-public-vehicle, road-map-of-evolving-complexity,
co-evolution, neural-networks, finite-automaton, multi-agent-system, evolutionary-computations,
artificial-immune-system, artificial-ants, swarm-intelligence}

\section{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.
\begin{quotation}
\noindent
{\it 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?}
\end{quotation}

\noindent
I want {\it 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.\\

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

\begin{quotation}
\noindent
{\it 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.}
\end{quotation}

\noindent
Public transportation problem is already quite an established field, 
as Pursula~\cite{purs} wrote:

\begin{quotation}
\noindent
{\it 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.}
\end{quotation}


\noindent
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 {\it 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.\\

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

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

\section{Methods}
\subsection{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~\cite{hill} 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. \\

\noindent
Since then, this concept of co-evolution has 
become familiar also in {\it Evolutionary Robotics}
(see, e.g. Bullock~\cite{bull} which also gives us 
not only an excellent survey on co-evolution but
discussed it as a computational design technique 
for evolutionary robotics.)\footnote{The term {\it Co-evolution}
was originally coined by P.~R.~Ehrlich and P.~H.~Raven (1964) in their paper
{\it ``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) {\it ``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)
{\it ``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.}.\\

\noindent
In our project,
the co-evolution will be intended as
{\it multiple bus-like-public-vehicle
not intelligent at the beginning}
versus
{\it 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.

\subsection{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:\\

\noindent
{\bf 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~\cite{rupp} for example.
\\ 

\noindent
{\bf 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~\cite{macl}
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.~\cite{stan}.) \\

\noindent
{\bf Artificial Immune System:}
Lei Wang at al.~\cite{wang}, for example, 
controlled Khepera robot with 8 infra-red sensors and 2 wheels
under {\it Braitenberg's model}~\cite{brai} with employing 
Artificial Immune System (AIS)
and concluded that 
{\it 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~\cite{ishi}.\\

\noindent
{\bf Artificial Ant Algorithm:}
Ant algorithms proposed by Dorigo~\cite{dori} 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~\cite{caro} 
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. \\

\noindent
{\bf 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.

\subsection{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.\\

\noindent
Analysis of the Behaviors of drivers have been reported fairly a lot:
Unsal~\cite{unsa} proposed three different {\it human driver models}
which were designed for an automated highway-vehicle systems (AHS);
Brackstone et al.~\cite{brac} models driver behavior 
in their Intelligent Transport Systems (ITS);
Al-Kaisy et al.~\cite{kais} evaluated ITS strategies 
by simulating {\it lane changing rules} of drivers at freeways.

As for pedestrian, 
D Helbing~\cite{helb}
modeled a pedestrian dynamics. \footnote{In their paper, authors give us 
also an excellent survey
of what they call {\it 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 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.}

\subsection{Evolution of Road-map}

{\it 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 {\it 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,
{\it 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 {\it a particle-based, multi-agent
approach to structure formation} using {\it 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 self-organization of of spatial structures.
Finally, in the last section {\it 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.

\subsection{Anomaly detection} 
Dasgupta~\cite{dasg}, 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:
\begin{quotation}
\noindent
{\it 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.}
\end{quotation}
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

\begin {quotation}
\noindent
{\it $\cdots$ extended AIS creates new detectors every day after the system experiences new network traffic which has not been presented before.}
\end{quotation}


\subsection{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.

\section{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.

\subsection{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.

\subsection{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?


\subsection{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 {\it Civil Engineering} point of view,
and in order for us to create a real innovative system, sometimes 
it is important to forget {\it what-have-been} but enjoy {\it what-could-be}.


\section{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.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=initial-road.eps,width=6cm,height=1.5cm}
   \caption{An example of road-map to start evolution with.}
 \end{center}
\end{figure}

\noindent
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.


\section{Summary}
In short, though not so short actually, 
our candidate sub-topics during the project are as follow.

\begin{itemize}
\setlength{\itemsep}{0pt}
\item How to design of public vehicle, passenger, and car.
\item How to evolve road system.
\item How to evaluate the complexity of road system.
\item How to co-evolve traffic system with road system
\item Simulation in real environment.
\item Consideration on why is simulation in-screen could be 
      different than on-real-desktop?
\item Consideration on how could be applied our results to a real world traffic system.
\end{itemize}
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.\\

\noindent
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.

\section{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.

\begin{thebibliography}{99}
\bibitem{purs}M.~Pursula (1999) 
{\em Simulation of Traffic Systems --- An Overview.}
Journal of Geographic Information and Decision Analysis, Vol.3, No.1, pp,1--8.

\bibitem{hill} W.~D.~Hillis (1991)
{\em 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.
%% pp. 295--312.

\bibitem{bull}S.~G.~Bullock (1995)
{\it Co-evolutionary Design: Implications for Evolutionary Robotics}
In proceedings of the 3rd European Conference on Artificial Life.

\bibitem{rupp}E.~ Ruppin (2001)
{\em Evolutionary Autonomous Agents: A neuroscience Perspective.}

\bibitem{macl} B.~MacLennan (1991)
{\it 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. 
%% pp. 631--658.

\bibitem{stan}K.~O.~Stanley and R.~Miikkulainen (2001)
{\em Evolving Neural Networks through Augmenting Topologies.}
The University of Texas at Austin, Technical Report TR-AI-01-290.

\bibitem{wang}L.~Wang at al. (2003)
{\em An Evolutionary Algorithm with Population Immunity and 
its Application on Autonomous Robot Control.}
In Proceedings of the IEEE congress on Evolutionary Computation.

\bibitem{brai} V.~Braitenberg (2000)
Vehicles: Experiments in Synthetic Psychology MIT Press.

% robot control by ais
\bibitem{ishi}K.~Ishiguro (1997)
{\em Emergent Construction of Artificial Immune Networks for Autonomous Mobile Robots.}
In Proceedings 1997 IEEE International Conference on System Man and cybernetics.
%% pp 1222--1228.

\bibitem{dori}M.~Dorigo (1992)
{\em Optimization, Learning and Natural Algorithms.} (in Italian)
Ph.D. thesis. Dipartimento di Elettronica e Informazione, Politecnico di Milano.

\bibitem{caro} G.~Di~Caro and M.~Dorigo (1998)
{\em An Adaptive Multi-agent Routing Algorithm Inspired by Ants Behavior.}
In Proceedings of 5th Annual Australasian Conference on Parallel and Real-Time
Systems.
%% pp. 261--272.

\bibitem{unsa}C.~Unsal (1998)
{\it Human Driver Models for AHS simulation}
Carnegie Mellon University: Robotic Institute
Technical Report CMU-RI-TR-98-02.

\bibitem{brac}M.~ Brackstone et al.~(2003)
{\it Driver Behavior and Traffic Modeling:
Are we looking at the Right Issues?}
In Proceedings of IEEE Intelligent Vehicles Symposium

\bibitem{kais}A.~F.~Al-Kaisy, J.~A.~Stewart, and M.~Van Aerde (1999)
{\it Microscopic Simulation of Lane Changing Behavior 
at Freeway Weaving Sections.}
Canadian Journal of Civil Engineering, 26(6), 840-851.

\bibitem{dasg}D.~Dasgupta and F.~Gonzalez (2002)
{\it An Immunity-Based Technique to Characterize Intrusions in Computer Networks.} 
IEEE Transactions on Evolutionary Computation, 6(3).

\bibitem{kim}J.~Kim and P.~J.~Bentley 
{\em Towards and Artificial Immune System for Network Intrusion Detection:
An Investigation of Dynamic Clonal Selection.}
\bibitem{helb}D. Helbing, P. Molnar, F. Schweitzer (1994)
{\it Computer simulations of Pedestrian Dynamics and Trail Formation.}
Journal of Evolution of Natural Structures 229--234.

\bibitem{helb-2}D.~Helbing, F.~Schweitzer, J.~Keltsch, and P.~Molnar (1997)
{\em Active Walker Model for the Formation of Human and Animal Trail Systems.}
Physical Review E 56, pp 2527-2539, 


\end{thebibliography}
\end{document}

AIS where antigen implys the problem to be solved and antibody means 
candidate solutions to this problem.

(5) etc.  (call for your creative/spontaneous idea/comments)
