\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 schdule 
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
trafic 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 monky 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 tuckle 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 characterised by a number of features that make them hard to analyze, control and optimise. 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, behaviours 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 standared 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 Inmmune 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 an exellent survey on co-evolution).\\

koko
Originally suggested by Leigh Van Valen. Natural selection continually operates on a species to keep up with improvements made by competing species, and each species environment deteriorates as its competitors evolve new adaptations. Named after the Red Queen's remark in Lewis Carroll's Alice through the Looking Glass: "Here



\noindent
In our project being porposed in this article,
the main idea of designing public transportation system is intended also by
this co-evolution.
The co-evolution will be 
{\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 vehicle can be driven?
The general concept is that a vehicle is  taken as a 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 mortor 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,~\cite{rupp} for example.
\\

\noindent
{\bf Finite-Automaton:} What attracts me more is to employ a finite-state automaton (FAM).
However, 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 eachother intelligently,
Thus far we know 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:}
In fact,
Lei Wang at al \cite{wang} controls Khepera robot with 8 infra-red sensors and 2 wheels
under Braitenberg's model \cite{brai} with employing AIS
and conclude that 
in an environment changes dynamically from time to time and 
the environment effects strongly on the robot:s behavior
AIS is theoretically better than the ordinary evolutionry algorithms on the learning capability form its experences.
partly because 
degeneration issue could be eliminayted more quickly than GA 
since AIS has the function of long-term memory 
while GA usualy can olly remember the gene information from its patent generation.
We can see yet another example of controling movile robot by AIS in~\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~\cite{caro} an adaptive multi-agent routing algorithm inspired by ants behaviour.
However, it is not difficult to employ the algorithm to control our vehicles in real-time. \\

\noindent
{\bf What else?}
Instead of employing those already explored technique mentioned above.
To find quite inovative methods of controlling our public vehicle 
is also one part of our project.

\subsection{What about other cars and human movement?}
Then what about passengers/pedestrians, and cars 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.


\subsection{Anomaly detection}
Dasgupta, for example, designed a multi agent system
for intrusion and/or anomaly detecion in a computer network
using AIS's reinforcement learning to sense its dynamic environment,
detect and eliminate pathogenes and memorize  them
for future recognition~\cite{dasg}. 
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 behaviours of network traffic on  one day, 
which are considered as self antigens, can be different from normal behavious 
of network traffic on another day. Therefore, the AIS needs to be extended, 
firstly to learn normal behaviours by undergoing onoly a small subset of self antigens 
at one time. Secondly its detectors should be replaced whenever previously observed 
normal behavious no loger represent current normal behavoious.}
\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$ his extended AIS creatres new detectors every day after the system experiences new network traffic which has not been presented before.}
\end{quotation}

\noindent
{\bf What else?}
Instead of employing those already explored technique mentioned above.
Could we think of the vehicles as Artificial Ants, 
Swarms, Autonomous Multi Agents, or whatever else.

\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{Descrepancy between in-screen and on-desktop}
Discrepancy between real simulations and ones in PC 
and why and how much is the difference. Simulation on
a real desk-top would be very limited physically and/or
financially, so simulations in PCs would be more preferable,
in general, but 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.
Such simulation as in this article is als interesting
from different aspect like {\it Civil Engineering} point of view.


\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 mortor output.
Second, we design a few passengers, pedestrians, and cars whose behaviors are
quasi-random but at least follow, not perfectly though, a trafic rule
which is determined by us in advance. Each of these not so inteligent 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=4cm,height=2cm}
   \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 increathing 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 trafic 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 trafic system.
\end{itemize}
Each team in our international corrabolation 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 downsized. 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{Acknowledgement}
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 encoragement.



\begin{thebibliography}{99}
\bibitem{hill} W.~D.~Hillis (1991)
{\em Co-Evoluving 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 Computattion.

\bibitem{brai} V.~Braitenberg (2000)
Vehicles: Experiments in Synthetic Psycohlogy 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 Internationnal 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{kim}J.~Kim and P.~J.~Bentley 
{\em Towards and Artificial Immune System for Network Intrusion Detection:
An Investigation of Dynamic Clonal Selection.}

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

\end{thebibliography}

\end{document}

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

better in changing environment than ec


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

===
Like Dasgupta (2002) who designed a multi agent system
for intrusion and/or anormaly detecion in a computer netwsork

Reinforcement learning to sense its dynamic environment,
detect and eliminate pathogtnes and memorize 
for future recognition.

Artificial immune network to cotrol robots walking
Ishiguro 1998
