A multi-agent approach towards modeling urban traffic scenarios

Deutsches
Forschungszentrum
fOr KOnstliche
Intelligenz GmbH
Research
Report
RR-92-47
A Multi-Agent Approach
towards Modeling
Urban Traffic Scenarios
Frank Bomarius
September 1992
Deutsches Forschungszentrum fOr KOnstliche Intelligenz
GmbH
Postfach 20 80
0-6750 Kaiserslautem, FRG
Tel.: (+49 631) 205-3211/13
Fax: (+49631) 205-3210
Stuhlsatzenhausweg 3
0-6600 Saarbriicken 11, FRG
Tel.: (+49681) 302-5252
Fax: (+49681) 302-5341
Deutsches Forschungszentrum
fOr
KOnstliche Intelligenz
The German Research Center for Artificial Intelligence (Deutsches Forschungszentrum fUr
KOnstliche Intelligenz , DFKI) with sites in Kaiserslautern and SaarbrOcken is a non-profit
organization which was founded in 1988. The shareholder companies are Atlas Elektronik ,
Daimler Benz , Fraunhofer Gesellschaft, GMD , IBM, Insiders, Mannesmann-Kienzle, Philips ,
SEMA Group Systems , Siemens and Siemens-Nixdorf. Research projects conducted at the
DFKI are funded by the German Ministry for Research and Technology, by the shareholder
companies , or by other industrial contracts .
The DFKI conducts application-oriented basic research in the field of artificial intelligence and
other related subfields of computer science . The overall goal is to construct systems with
technical knowledge and common sense which - by using AI methods - implement a problem
solution for a selected application area. Currently, there are the following research areas at the
DFKI :
o
o
o
o
Intelligent Engineering Systems
Intelligent User Interfaces
Intelligent Communication Networks
Intelligent Cooperative Systems .
The DFKI strives at making its research results available to the scientific community. There exist
many contacts to domestic and foreign research institutions , both in academy and industry . The
DFKI hosts technology transfer workshops for shareholders and other interested groups in
order to inform about the current state of research .
From its beginning , the DFKI has provided an attractive working environment for AI researchers
from Germany and from all over the world. The goal is to have a staff of about 100 researchers at
the end of the building -up phase .
Prof. Dr. Gerhard Barth
Director
A Multi-Agent Approach towards Modeling Urban Traffic Scenarios
Frank Bomarius
DFKI-RR-92-47
Parts of this report have also appeared in:
A. Lux, F. Bomarius, D. Steiner: A Model for Supporting Human Computer
Cooperation. in: Proceedings of the AAAI 92 Workshop on Cooperation among
Heterogeneous Intelligent Systems, San Jose, CA. July 1992.
F. Bomarius, D. Steiner: A Model for Supporting Human Computer Cooperation. at:
ECAI-92 Workshop: Application Aspects of DAI. Vienna. August 1992.
F. Bomarius. Using the MECCA System to implement Urban Traffic Scenarios. DFKI
Technical Memo TM-92-07. September 1992.
This work has been partially supported by the European Community as part of
ESPRIT II Project 5362 IMAGINE.
© Deutsches Forschungszentrum fOr Kunstliche Intelligenz 1992
This work may not be copied or reproduced in whole or in part for any commercial purpose. Permission to copy in
whole or in part without payment of fee is granted for nonprofit educational and research purposes provided that
all such whole or partial copies include the following: a notice that such copying is by permission of Deutsches
Forschungszentrum fUr Kunstliche Intelligenz, Kaiserslautern, Federal Republic of Germany; an
acknowledgement of the authors and individual contributors to the work; all applicable portions of this copyright
notice. Copying, reproducing, or republishing for any other purpose shall require a licence with payment of fee to
Deutsches Forschungszentrum fUr Kunstliche Intelligenz.
A Multi-Agent Approach
towards Modeling
Urban Traffic Scenarios
F. I30mari ns
D FE] h:aiserslall tern
Septcrrlher 1992
Ahstract
This paper investigat es th e us e oj th e multi-age nt paradigm in modeling urban traffic
scenarios . It demonstrat es that vehicles, pedes trians, traffi c-lights, car-parks and eve n str·ee ts
can be considered ag ents in a heterog eneo us multi-agent sys tem . Differen t types oj agents in
such scenarios will be identifi ed, characl en zed and co nstru cted by vIrtu e oj a genera l agent
model .
The various kinds oj relationships and mtera ctions, generally called. cooperations between
these ag ents will be modeled; some examp les sketch th e major issues · deve loped in thI S paper.
Contents
1
Investigating Urban Tra ffic
2
2
Using Age nts to Mod e l Traffi c S cenarios
2. 1 Th e No ti o n of Age nts . . . . . .
2. 2 A G e nera l Agent Model
2.3 The Soc iety of Coo pera ti ng Age nts
2.4 User Age nts . . . . . . .
(i
3
Example s
3. 1 Multi-Agent Sce nari o: C rossroads . . . .
3 .2 Multi-Agent Sce na ri o: Car App roac hin g a C ity
3.3 Agents in th e Urb a n Traffi c Scena ri o ..
4
R e se arch Projec ts in the Fie ld of Traffi c C o ntl'ol
4. 1 PRO M ET II E US
4.2 LISB . .
5
Conclusion
A Towards an Imple m e nt a tio n
A.l Street Age nts . . . . .
A .2 C rossroads a nd T -J un cti o n Age nts
A.2.1 C rossroads Age nt . . . .
A .2.2 T -Jun ctio n Age nt
A .2.3 Computing Flow Volumes
A.3 Ve hicl e Age nts
A.4 Concl usio n
7
7
8
K
!)
I()
1G
17
17
I ii
I i)
I!J
I !)
'2'2
'2 :\
Chapter 1
Investigating Urban Traffic
To participate in traffic , in particular in urban areas with a high volum e of traffi c, is a highly interact ive
task. Various types of road users have to continuously adjust their actions in order to avoid crashes
and to get on to their destinations . From the point of view of th e individual, he or she merely watch es
the environment and reacts appropriately in order to achieve his or her goals (to get on to some place,
survive, etc.). These local goals are th e driving forces that let th e individu a l move a nd behave in ce rt a in
ways.
In most situations this strategy is successful since human beings, like m a ny other beings, have
developed appropriate behaviors throughout th eir evolution that allows the individual to proceed in the
face of arising conflicts. Som e inh e rited and some learn ed behaviors plus some additional rul es (e.g.
traffic regulations) suffice. So , in most cases, traffi c flows and th e parti cip a nts achieve their goals.
However , sometimes too many individuals with too many co nfli cting goals m eet. This us ually results
in a traffic-jam or, in severe cases, a crash. The latter will no t. he inves tigated here; the form er seems
worthwhil e thinking about, since it has to do with unintenti o nal misb ehav io r (misguidedness) due to
a lack of environme ntal information . In o th er word s: no body wo uld vo lunta rily j oin a t.ramc-jam if he
or she knew in advance that it will occur. Thu s, a nti cipat io n is an imp o rt. a nt facto r for the reactive
behavior of road users. At prese nt , th e scope of anticipation is limited to th e ra nge o f the hum a n se nses,
in particular seeing and hearing.
Participating in traffic is , to a great ex tent, a matter of co mmuni cati on . Humans ha ve com llluni cat ion
channels that, in th e past , perfectly served needs with regard to bandwidth, sensitivity, speed and ran ge .
They turn out to be insufficient in th e face of hi g h volumes of traffi c including fast m ov ing vehicles and
great numb ers of individuals . In such complex situations human s can not a nti cipate, from their local
point of view, the overall be havior of th e maj o rity which is necessary in o rd er to react in a timely
fashion . Radio traffic services try to ex te nd th e 'se nses' of the individu a l by providing info rm at io n
about situations that lie beyond th e individu a l's range. Unfortunately, these services tend to be s low
and misguiding. They often provid e inform at ion wh en it is too late to react appropriately. In some
cases the situation gets even worse du e to outdated informati o n o r ove r-react ions o f the rece ivers.
Information provided by those servi ces is coarse grained and unsp ecifi c fro m the point o f view of
the individual road user. In order to find an optimal or at least a good route, with respect to tim e and
distance, each road user requires different sorts of info rm at io n. At. prese nt seve ra l sources of informat io n
are available:
1. The well known radio traffic services provid e a general overvi ew o f the current traffic s ituati o n ,
similar to a snapshot. This overview is of limited use fo r th e individu a l in fo recast ing future traffic
situations since it does not take into cons id erati on the dpstinat.ions a nd plann ed ro ut.es of the road
users currently o n their way.
2 . Since each road user has common sense ~;no1li l e dg e, he or s he ca n a nti cip a te s lt.u at lons t.hat. arp
likely to happ en on a reg ular basis. Fo r exampl e, eve ry Ill or nin g and a fte rn oo n ru s h-h o ur traffic
must be expec ted . At th e beg inning and end o f vacat.ions o r Oil ho lidays like C hri st.m as, ce rt a in
typi cal traffi c situations can be foresee n .
2
3. In much the same way, experiences about peculiarities of regularly used routes like road-works,
traffic-lights that are not adjusted to th e varying traffic volumes, notoriously overcrowded car
parks and the like have influence on decisions of the individual.
4. Observations of the environment, e.g. the weather or an accident up ahead, may be of immediate
impact on decision making.
Based on this information, each road use r plans a route, selects a means of transport and calculates
the estimated time needed. While en route deviations from this plan are usually not possible. In
particular, the road user nowadays wOllld not get enough information to redo planning and come up
with an alternative, more viable, plan.
This is where computer and communication tec hnologi es CO IIl(-' in. If each road user could be emb edd ed
into a network of te lecommunication links that spread allover the collntry and connect every relevant
passive or active entity involved in the traffic scenario then significant improve ments are conceivable. [n
the fol[owing chapter such a network will be olltlined and some expec ted advantages will be po inted out.
The main goal of this paper is to demonstrate the applicability o f the maj o r concepts of the so called
multi-agent paradigm for the application domain 'u rban traffic scenario' (UTS). Du e to th e co mpl ex ity of
the problem domain it is not possible to give a comprehensive treatise. lI e nce, many interest ing aspects
can not be mentioned here which should also be invest igated, such as vehicles moving on autopilot
or systems for automatic collision prevention. This paper will, therefore, foc us on a choi ce o f aspects
abandoning (but not ignoring) th e ot hers .
Two major areas of research have impact on the UTS domain, nam ely electrical eng in ee ring (telecommunications in parti cular) and compllter science:
Electrical Engineering Most of the technologies that have to be t.aken In consideration here have
already reach ed high standards and are, for a large part, ready to use :
• Remote Sensing
• Signal Process ing
• High Bandwidth Radio Comm unication
• Networking
In the following it is assllmed that. t.ll('se t.ec hn o logi es are fn 'e ly availahlf' as ready-to-llse co mpon e nt.s
which interface easily to computers. All data sampled or transrnit,t.ed hy these components originat.e
from or are hand ed to these computers. Low le ve l issu es like message fo rmats, m eans of transmission
(radio, infra-red light, etc.) and inte rfacing t.o co rnrllte rs (in cillding co nve rsion of signals to symhols)
will not be m ention ed here.
Ubiquitous computing power is assumed [1], so every entity involved in the traffic scenario is eq uipp ed
with a local (or has direct access to a re mote) computer which is in direct. contact. wit.h the e nt.iti es'
computers in the environment.
Computer Science adds to th e above listed issues the concepts, m et hods and technologi es to ex ploit
and hopefully control what is technically feasibl e. In parti cular, the following areas of research are
relevant here:
• Distributed Artificial [ntelligence (DAI)
• Computer Networks
• Distributed Processing
The above mentioned ubiquitous compllting reqllires rowe rfllimod eis of int.eract.ion ht't.ween the vast
amount of entities involved in traffic scenarios. Research in DA[ , distributed processing, a.nd computer
networking has rece ntly begun to reveal the prerequisite technologies to tackle th e probl e ms at hand.
3
The details of comp ute r networking and dist.ributed process ing are Il o t illv('st igated he re. Emphasi s will
be put on the DAI concepts.
It is the goal of this paper to app ly DA I concept.s t.o th e UTS. Th e discllssi o ll will he accoillpallied by
some examples that demonstrate the appropriateness of the maj o r co ncep ts of th e multi-age nt pa rad igm
in the traffic control scenario.
Note that since this paper is a first approach to app ly multi-agent syste m techn o logy to a real
world scenario of very high complexity, simplifications will be introd uced in o rd er to kee p t.he exa mpl es
comprehensible. Nevertheless, the author believes that a ll co ncep ts prese nted here eas ily scale up (. 0
and perform well in real world conditions.
4
Chapter 2
Using Agents to Model Traffic
Scenarios
DIstributed computmg scenarios have bec il ulld cr illvcst iga.l.i o ll fo r a IOll g l.i II I!'. 1I111. . dll!' 1.0 lilt' lar k o f
technical feasibility of distributed systems t.hat, arc cO lliprisC'd o f a cO llsid t' rahl(' 1I111111)(' r of (,() IIIPIlt.ill g
nod es, research was foc used on probl ellis that were tractablt' 0 11 a tllt'o rt' l.i cal hasis . A siglliricallt.
property of the res ults of this wo rk is that, in m os t. rases, t.h t' res ult.illg Iliult.i - pro('t'sso r sy:-; l,t'llls rt ' ly
on regular intercon nec tion patterns and are CO lli priscd o f id ellt.ical (sp('c ial pu rp ost' ) COlli pll t.i IIg 1I0 dt's .
Th ese homogeneous systems co uld be real iu'd with rcaso llahlt' dfo rLs alld W( ' f'( ' succ('ssflll ill Vt'ry spt'ci rir
application domains.
Rece ntly, h et erog en eo us co mpu ter Il ct wo rks whi ch arc COlli pris('(1 o f d i rr(' r(' llt k i lids o f gt'lIt'ra I pllrp OSt '
co mputing nod es th a t are intcr co nn ec ted ill nOll - reg ul a r a lld /o r f'('g lilar fa.s hi o lls h,w(' ht't'li illv('st.ig'LLt 'ti.
The res ults of DAI (in parti cu l ar distributed prob lc nl so lvillg) alld, 1.0 SOIlI!! cxtC llt , wo rk ill tilt' rit'ld
of I1CCW (human computer coop erative wo rk) [8] [7] rro lll otcd th e J evci Oplll<'lIt o f CO II Ct' pt.S fo r Lllt's<'
het erogen eous computer networks. Th e term multi-ag ent syste1l/ was coillt'd t,o tkllot,(, rO ll rt' pl,lIal wo rk
in this fi eld [2].
Whereas the above m entioll ed 'cl assical' distribllted complltillg is of mill o r lise USt' ill hct.t'rog<' II('OIiS
domains such as traffic control, multi-agcnt. systelll t cc hn o logy provid cs a mil ch IIIOJ"( ' appropriat.t' approach.
In the following sections a bri ef in t rodu ct.ion to rnulti -aW~ IIt. syst.ems, MAS fo r short., is givell. Nex t.
th e MAS approach to th e traffi c scenario will he dcvc lo r ed .
2.1
The Notion of Agents
At present, th e MAS-resea rchers have no t. yet settled Oil co ll cise and III1 0 ppos<,d ddinit.iolls. So tilt'
t erm agent is used in an intuitive fashi o n [2] . It refers t.o th l' COlllpllt.at.iolial rC' prt's(' IIt.at.io li (silllldat.ioll)
of some entity in th e rea l wo rld . The ag<'IIt" lik(, t.h c rcsp('c t,iv(' rt' a l wo rld ('IIt.it.y, t' x llihiLs o hs('rv a ld( '
behavior. Note that this elltity does not have to have substance, it IIIa.y he all ahst.ract CO ll ce pt su ch as
a bank account.
Agents may be co mrared to objects known from th e do rnaill of object-orient.t'd progralJllllilig . I II
fact agents can be impl em ented as objects. Ilut agents are co nsid ered to be a high er level co nce pt III
that they abstract from th e impl em en t ati o n details entail ed by th e t erm 'o bj ect'. Agents are mu ch m o re
sophisticated, th ey are autonomous and often thought o f as ' intelligent' , they are co mprised of logi cal
components whose impl em entations may be neg lec t.ed.
Agents stand for a wid e variety of real wo rld entiti es. In th e trarri c scen'ario agellts /nay be intelligent
robot-vehicl es as well as rath er simple traffic-lights or parking lots . Even humans may be considered
agents. I So the model of agents has to fit a broad spectrum of relevant entiti es in th e wo rld o f discourse.
1 Note that the author does not think o f humans th e m se lves as agents in the MAS sense. Ilumans are considered
equipped with a machine agent , whi ch a c ts o n th e ir b e half and interfaces its use r to th e MAS. This special type of agent
is called user ag ent (see also Sec tion 2.4).
5
Communicator
Head
Body
Figure 2.1: Agent Stru ct ure
2.2
A General Agent Model
Every entity in th e wo rld inte racts with its enviro nm ent. Inte rac ti o n m ay be o n its own beha lf (ac tive
entities) or du e to external stimuli (re-active o r pass ive entiti es). Interac ti o ll m ay he thro ug h diffe re nt
kinds of m edia . In th e world of co mputer- based age nts m ess ag e-t ra nsmIssIO n oetweell age nt.s is t he us ua l
(a nd suffi cient) way to m o d el interacti o n . (Oth ers a re co nce iva bl e as well , but will no t. bp in ves t.i ga t.~~ cI
here. )
Closely related to interaction is the obs ervable beha vio r o f a ll enti ty . Th is is th e way it. ( re-) ac ts ill
given situations. Given th a t an agent interacts o nly by m eans o f messages, its beha vi o r is a nl app in g
from received m essages to emitted m essages . It is assum ed th a t (m ost o f) t his beha vi o r is expli cit ly
represented in the computer-based agent .
Since, in the real world, nothing gets a ltered by pure m essage pass in g, som e fun ct ion ality mu st be
introduced into th e mod el th a t eith er imp oses cha nges to th e p hysical wo rld (by m eans o f ac tu a to rs) o r
co mputes new info rmati o n th a t m ay be co mmuni cated. Thi s age nt-s pec ifi c fun cti o na li ty is th e m eans
by whi ch the world stat e is a ltered .
According to these observa ti ons every age nt can be divid ed into three m a in co mpo nents, na m ely
communicator, head and body whi ch impl ement m essage- tra nsmi ss io n, t he o bse rva bl e be ha vi o r a nd t he
fun ctio nal ity resp ec tively . Figure 2.1 sket ches th e agent stru cture o n thi s abs trac t leve l. III thi s model
a ll interactio ns are m o deled by m eans o f m essage pass in g.
Communicator Th e communicator is in charge o f establi shin g a nd m a inta ining th e phys ical comm unication chann els to oth er agents in, th e environm ent . It co ntinu o usly ' li ste ns' fo r in co min g m essages,
delivers them to the head , a nd e mits m essages o ri g in a ting fro m th e head .
For the whol e agent to communi cate effici ently , its co mmuni cato r has to provid e a s uffi cientl y a bstrac t
communicati on interface t o the agent 's head . Th a t is, it has to hid e a ll techni cal det a il s o f co mllluni cati o n
and provid e reliable tra nsmissio n chann e ls to o th er age nt.s in th (' (~ lIvir o nlll e nt..
Head
Th e head , re li eved fro m primitive co mmuni cati o n t as ks by virt.u !' o f th e co lliniuni cat.o r , has 1.0
plan , negotiate and interac t on a high leve l o f a bstrac ti o n . It. rll ay i> f' co ncf' ived as a kn o wl f' d ge- has('d
comp o nent , being aw a re o f goal s, inte nti o ns, fun cti o na liti es a nd reso ur ces o f it.s assoc ia l,eJ ho dy a lld o f
o ther agents as well. It strives to a chi eve local a nd /o r co mm o n goals, whil e ac till g s imllit.a ll co ll sly ill
differe nt interactions . This , all together, comprises th e o bserva. bl e beha vi o r o f a n age nt. .
Knowledge based decision m a king compon ents are consid ered necessary o nly fo r so phi st.i cat ed age nts .
Simpler agents, like e. g. a tra ffi c-light , mi g ht do with o ut kn owl ed ge based co mp o ne nts. Th ey will
6
not participate in compl ex negotiations with oth er agents, but will rath er reac t 0 11 a sm a ll number o f
m essages th ey understand . Th eir behavi o r is representabl e by m eans o f hard -coded procedures; planning
and knowl edge-based dec isi o n making see m dispensabl e.
Body Th e agent 's bo dy constitutes th ose parts o f its o verall fun cti o nality it lH' rfo rm s in o rd er to
(intentio nally) alter th e wo rld state. Whil e co mmuni cat o rs <l lId eve n IH'ads m ay h C' quit.e sirnil <l r fo r
differ ent typ es o f agents, th eir bo di es will differ sig nifi cant.l y.
In th e tr affi c scen ari o, fo r ex a mpl e, o nl y vehi cles have fUIl c. ti o li a liti es th at ena hl e Ill o t.i o n , whil e
traffic-lights , stree t s o r p arkin g lo t s do no t . Bo di es o f vehi cles a nd t.r am c- li g ht.s bo t.h (' Illit. o pt.i cal
signals . Humans and vehicl es m ay also empl oy aco usti c sig nal s and ges tures.
It is notewo rthy th at th e m o del prese nted is by no m eans do m a in spec ifi c. In part.i cllla.r , t.h e ag(' nl.
stru cture allows t o desc rib e agents of alm os t any do main ill a ge neral fashi o n .
2.3
The Society of Cooperating Agents
Multi- agent sy st em s are o ft en par aph rased by th e llI et a ph o r 'soc ipty o f coo per ati ng age nt.s ' .
m etaph o r stresses th e m os t pro min ellt. as p('c t.s o f IlIult.i -agt' ltI. sys t.elll s:
Th is
H e terogeneity: A M AS is a het erogeneo ll s co ll C'c t.io li o f (lgC' lIts. F,ac h age llt has sp ec ifi c pro pnti('s
(b ehavi o r , capa biliti es, a uth o ri ti es ) th at d ist i ng u ishes it frOl1l o t.h er age nt.s. Si III i l ar (lg(' nts lIl ay 1)('
co nsid ered as being o f a co mm o n typ e. Po r ex alllpl e all t.r a ffi c light.s in UT S ;u e o f t.1J(' salll< ' t.y pe.
Cooperation: Agents inter act. So m e int.f' r <lct. io ns will he coo lw rat.i o ll s Iw t.wC'c n (l1.!;<' IIt.s wo rking
0 11 a
comm o n t ask o r goal. A gen ts coo per at.!' in o rd !' r t.o ac hi< ' v( ' goa ls tl l<'y cO llld 11 0 1. aelli('v(' 0 11 1.11( ' ir
own. Fo r in st ance in th e UTS all t. raffi c- li g ht.s o f a cross roads IIl <1y coo per at.(' ( hy adjn st.in g t.1 1<'
timing o f th e li g ht sC'qu encC') in o rd er t.o lIl aXillli ,,(' t.hro ll g llpllt. a.nd Illillillli ;t,(, t.11<' lik (, lih oo d o f
tr affi c-j am s.
Grouping: Coo peratin g agents lll aY j o ill t.og<'l.hn and fOrtl1 g ro llps . 'I'l l<' g ro llp l'd ag< 'lll.s co ll al> o r al.(' in
o rd er t o achi eve co mm o ll goals. Th ey Ill ay hI' r(' pn's(' nt.(!d I>y a spec ia l ag(! ltI. calkd t.11<' .IImlt71 IU/ FIII
whi ch is th e represe ntat ive o f th e g ro llp in int.C' r act. io IIS wit.h o t.II(' r ag(' lIts o r g ro llps. All indi v idll a l
agent may be m emb er o f different g ro ups sillllllt.all eo llsly . Fllrt.il<'rtIl Ore, g ro llps IIl ay fOrtll higll<'r
ord er groups . Fo r ex a mpl e, in th e UTS , parkin g lo t s lTl ay j o ill int.o a car- pa rk alld all car- parks o f
a city m ay j o intly inter ac t in o rd er t o bal ance pa rkin g space occ llp at.i o n .
2.4
User Agents
Humans are integrat ed into thi s ' m achin e soc iety ' hy m eans o f use r ag ents. Th ese age llt.s can he
consid ered prosth es ises th at wid en th e r ange of hum a n se nses by providin g info rm at io n th ey co llid not
gath er o th erwi se . Info rm ati o n is g uar anteed to be IIp- t o- d at e and is filtered acco rdin g t o th e current
needs. So a user will no t be overwh elm ed with o lltd at ed o r irrelevallt d at a, bllt will rece ive illfo rmati o n
that concerns th e goal at hand , i .e. reaching th e cllrrent des tin at.i o n .
Furth erm o r e, th e user agent will , depending o n it.s level o f so phisti cati o n , act int.elligently o n behalf
o f its human user . Thu s, a use r age nt can be r q~a rd (' d as all ' int.elli ge nt. ass ist. a nt ' o r 'juni o r partn cr ' o f
th e human user [3] .
In th e UTS do m ain a user age nt mi g ht be buil t into cars, o r mi g ht be publi cly ava il ab l(! at bll s
sto ps and und er g ro und st ati o ns t o prov id e use rs wi t.it t.lw rC' q II i r ~ d in fo rm a t.i o n . In t.11<' fll t.1I fI ' it. is
co nce ivabl e th at every bo dy carri es a perso nal use r age nt , th at. co nt.inu o usl y co nn ens t.o o t.tl<'r age nt.s ill
t he enviro nm ent [1] .
In th e nex t cha pt.c r we rev isit. t.ll(' ahov(' 1I1 (' nt.i o lH'd as pec t s ill th (' co nt.ext. o f SO li I<' (' xelllpl ary tr affi c
situ ation s.
7
Chapter 3
Examples
3.1
Multi-Agent Scenario : Crossroads
Figure 3.1 shows a typical traffic si tuation at an inte rsection . A Ithough it capt u res on Iy a sllIall part
of the overall traffic scenario it allows to demonstrate the applicability of most of the MAS co ncepts ill
the UTS.
Grey arrows indicate goals of the agents whil e black arrows visualize co mmunication links .
There are two ea.,tward bound cars: car-l and car - 2 . As indicated by the gray arrows car-2
intends to cross NS -St reet, while car-l intends to turn right into NS-Street . J30th cars are agents
that communicate with the next traffic-light agent ahead, i. e. tl-1. So tl-l gets informed about the
intentions of car-l and car-2 . car-3 which inte nds to turn left into EW-Street in order to occupy the
free parking lot communicates with tl-2 .
Traffic at the crossroads is cont ro ll ed by the cooperation of the four traffic-lights. All fo ur trafficlight agents negotiate about the length of th e phases of the next light-seq uence in o rd er to minimize
waiting-time for the cars.
Since there a re cu rrent ly no cars app roaching tl-3 and tl-4 , th ese li ghts will not impose furth er
constraints on the determination of the next li ght sequence . So tl-l and tl-2 wi ll decide if they give
preference to car-3 or to car-l and car-2 .
car-3 is in contact with the car-park because its drive r wants to park the car. car-park is an agent
which communicates with app roac hin g cars on behalf of th e set of parking lot agents. It rep rese nts
a ll parking lot agents that compr ise th e car-park .
This type o f agent is call ed a group agent. CroliP agents are respons ibl e for the coo[le rati o n among
group membe rs and for the cooperat ion of th e groll[l wit.h the worlo. A g ro ll[l agent. hid es I.ht' df'tails
of the group organ ization and provides a (sophisticated) service to cli ellts of t.he grollp. Depe nJing o n
the o rganizational princ iples of th e g roup, the group agent Illay have t.he allthority t.o give o rd e rs t.o the
group members or it may inte ract with them on a peer-to-peer ba<; is. The grollp age llt rll ay bf' a specia l
agent designed to organize group behavior or it m ay be one 0111. o f I.IIP grollp that has hpt'll sciectt'd (1'-;
group representative.
The fou r traffic-lights form a g roup a'S well but, as opposed to th e car-park g rollp, t.h ey 00 1I0t have
a rep resentative agent . Each membe·r of th e group commun icates with th e world on its own behalf alld
on behalf of the group. Here, gro up behavior is determined by pee r- to-peer negot iations , i.e. the groll[l
members have equal rights and responsibiliti es.
The scenari o of Figure 3.1 exemplifi es how cli ent agents (cars) contact agents with high er authority
(traffic-lights) in order to rece ive o rd ers (light signals from the traffi c- lights). It gives two examp les of
how agents may organ ize into gro ups. Th e traffic-lights make up a grollp o f eq ual members where each
member communicates with clients , whereas th e car-park rep resents a nd governs a g ro up of parking lot
agents. For the parking lots, communication is restricted to the car-park group .
Thus, this scenario is an illust ration of the main aspects of multi-age nt systems which were li sted ill
Section 2.3. It shows a heterogeneous set of age nts that coo perate , some of them joining into groups .
8
t
NS-Street
north
(11-3)
~
(tl-4)
'e oe'
EW-Street
(car-I)
(tl- I )
free
parking
lot
car-park
figure :\. 1: ( ;ross roads Sce liMi o
Figure 3.2 is a variation o n the pre vious e xampl e. An ad diti onal car age llt , ambulance , has hee ll
added to the scene. It inte nds to cross EW-Street a nd wants to take prec('de nc(' o v(' r a ll ot. lw r cars
cu rrent ly approaching the inte rsection. Th e ambulance introd ll ces an e xccp tion to LlII: stalld ard o pc rations o f th e traffic-lights: t hrou gh comm uni cat.ion with th e t.ra ffi c- li g ht.s t.h e amh ili a li ce g iv('s 1.1 1<' o rd( ~ r
to immediately blo ck al l dircct ions .
This exemp lifi es th e way ho w ce rt ai n ag(! nts may ove rrid (' st.alld ard o lw rn.t.i o ll s , at. leas t. ill a lilllit.<,d
region, du e to th ei r hi g he r a u thor it.y.
3.2
Multi-Agent Scenario: Car Approaching a City
T he exampl e dep icted in Figure 3.3 g ives an ove rvi e w o f what hap pe ns wh c n a m o bil(' age llt. a pproaches
a city. A pre requisite to this exampl e is a sta ndard rn echa nis lll fo r cll a blillg t he rn o hil (' ag<' lIt. 1.0 cO lltact,
t he traffic cont ro l agents.
As Figure 3.3 suggests , a hi e ra rchi cal o rgani7.ation o f th e t raffic co nt. ro l agent.s is ass llill cd whi ch
res ults in the grouping o f subordinate age nts und e r th eir s up e ri o rs. I Not o lily th e imrn ob ile agents rlre
part o f that hi e ra rchy but a lso pedes trians a nd a ll kind s o f ve hi cles. As o pposed to th e immohile age nts
they a re o nly te mporarily assigned a p lace in th e hi e rarchy . As th ey move, t he ir place m e nt in th e age llt
hiera rchy changes, e .g . t hey leave town , become imm ob ile whil e parking, o r pass fr o m o ne distri ct to
a nother .
Whil e app roachin g the o uts kirts o f t he city , th e car in Figure 3.3 has· to registe r with th e traffic
flow control agent. This agent samp les d a t a abo ut a ll mobil e age nts e nte ring o r leaving th e urb a n
regio n . Each o f th e m has to declare its des tination(s) , prefe rred route(s), speed, es timated tim e o f
I T h e hi erar chy s h ow n in Figure 3.3 is fo r illus trati o n purp oses o nly and is no t co nsidered to be a reali s tic mod e l. In
parti c ular a MAS-hierarchy fo r a reali s ti c t own is mu ch to o co mpl ex to be depi c ten clearly within th e limited s pace o f this
pape r.
9
t
north
(tl-3) ;
(tl-4)
-~I.Q.I
EW-Street
(car-I)
(tl-1 )
free
parking
lot
car-park
Figure 3.2: Crossroads with app roach in g Ambulan ce
departure etc . The traffic flow control agents calcu late a rOIlt.e for the approaching agellt based
on their current knowledge about the (estimated) traffic volum e and parking space occupation.
Based on the calc ulated route, the approaching agent is brought in contact wit.h the subordinat.e
agents responsible for the districts th e agent will pass through.
Assuming that each agent gives hon es t. informatioll about its inte ntions, t.h e collsequences for traffic
flow control may be far reach i ng . 2 l1ased on this information, t.ra ffi c volu mes can be forecas t and traffic
flow can be contro ll ed so that it comes clos(' t.o an orti1I1l1III wit.h resp ec t, t.o g lo bal throughput and
traffic-jam avoidance. In particular , excc rt.iollal eve nts , e.g. road works, can be t.ake n into co nsid e ration
when calculating routes for mobile agents.
Furthermore, foreign road users, not familiar with their rOIlt.e, may be continuous ly gllided by the
traffic flow control system bringing them direc tly to th eir destinations.
Even accidents will not unconditionally lead to traffic-jams . Th e continuous superv ision of mobile
agents in the proximity o f the accident a llows calcu lating individual det.ours for these agents Illit.igating
the effects on traffic flow.
The benefits of a MAS organization o f the UTS for traffic flow contro l seem to be e normous but a
comp lete treatise goes far beyond the scope of this pap er. In the next section th e individual entiti es of
the UTS are investigated in detail with res pect to the MAS aspects .
3.3
Agents in the Urban Traffic Scenario
In the examples given above, some of the ent iti es in the UTS have been describ ed as agents. This section
summarizes the results and investigates each type of agent individually.
2The author assumes benevolent agents. For some domains this might be an unrealisti c assllmptioll , bllt it is an
appropriate o r even necessary ass umpti on in scenarios where reliable for ecasts are (.0 be mad e.
10
Figllrf' 3.:l : Ca r app roa.ching
CI
Cit.y
Vehicles Vehicles, i.e. any mobile agent except pedestrians, arc agen ts that in co rpo rate I.he necessary
comp utational power a nd telecommunication fac iliti es to estab li s h and s ust a in co ntact with a conside rable number of agents in their en vironm ent. The speed with whi ch vehicles move req uires not o nly that
they be ab le to ha ndl e a great nUlllbe r o f COfl lllluni cat io ns in pa ra ll e l, b ut a lso to freq ue ntly make ne w
'acq uaintan ces' a nd terminate commu ni cation s rap idly.
Since vehicl es rely on guiding info rm at io n fr om their enviro nm ent , i.e. mostly fr om the imm ob ile
agents, they are to some exten t subordinate to these. It is a matter o f futur e research how to properly
adjust the a uthority levels in o rd er to not ove r-co nst rain t he vehicles.
Pedestrians For pedestrians to become part o f the M AS-world in th e sam e way as desc ribed for
vehicles some technological progress is req uired. Each perso n wou ld ha ve to carry a so rt of pocket
computer (whose computational power is beyond what is commerc ia lly avai lab le a t present) that makes
its owner an agent in the MAS (cf. Section 2.4). Aside from the political a nd soc ia l discussions about
supervision of individuals that s uch a device wo uld trigger, it may be claimed that, at least for the
purpose of guiding people to a destination, it is a valuable co ncept. Many more a dvant ageo us prope rti es
o f this dev ice are conceivabl e, e.g. benefits fo r ha ndi capped persons.
Since such a device wo uld turn o ut to be a universal communi cat ion faci lity , it a ll ows its own er not
on ly to interact with the imm ed iate en vironm ent, performed mostly a utomat ically by th e device, but
a lso provides access to info rm ation systems a t. a ny timf' at. a ny placf'. For in stance sched ul es o f public
transport systems may be accessed a nd rese rvat io ns cO llld be m ade in stant a neo usly with the he lp o f this
device.
Note that eq uippin g persons with a po rl. ilh le 'llser age nt. d('viCf" is o pt.i onal in t.l1<' t.raffic ('o lltrol
scen a rI o.
Traffic-Lights The ro les o f traffic-light agen t.s have already been described in the ahove exampl es. The
task o f a sin g leto n traffic-light. is rather simp le. It. has t.o recogn i;w ( i.e. cO llnl.) app roach in g ve hi cles (and
pedestrians). Based on their estimated a rriva l times the timin g o f I.h e li g ht seq uence a t. the cross roads
can he adjllst.ed ap propri a t'f' ly . Sinef'. in most, easps. a t.raffie-light. hf'longs to a g ro up it can not, alter
the light seq ue nce timing o n its own but has to negot iate with its part.ners. Each traffic-light agent
kn ows about the traffic volume app roac hing fr om t.he direction it is co ntro lling . The integ rat ion o f the
kn ow ledge of all m embers o f the group a ll ows t.o calc ul ate the timing o f light seq uences that is opt im a l
with respect to overall throughput.
Unfortunately, the local op timizations at each crossroad will not lead to globally opt im a l res ults.
Therefore, the d ep endencies that exist between sequences o f cross roads (lined up along st ree ts) have to
be taken into considerat ion.
II
Streets Introducing streets as agents is promising; because it helps solving the problems of flow co ntrol.
Since mathematical models of flow are based on a not.ion o f a sort of' pi pe' t.hat ha.<; measu rabl e properties
like maximum throughput, optimal flow speed etc. it see illS nal.llral to illtrodllce street-agellts that. lIlodel
these very properties .
In the context of multi agent systems , streets are th e means by which to group cross roads, i. p. tiw
groups of traffic-light agents, into higher level groups thus weav ing a web of coope rating traffic ag(' nts .
Furthermore, st reet-agents introduce approaching vehicl es to th e imlllohile agenl.s lin ed lip along
the street. Thereby mobile agents will a lw ays get acquainted with the relevant agents along their way
without thp nepd t.o 'sparch' for t.h(,lll . St.r('Pt.s can givp fpedhack to 1.11(' mobil e agent. 1.0 Iwlp dct.e l'llIill('
its current locus, speed and heading.
Parking Lots Besides the traffic-light group the first example (cf. Figure 3.1) introdu ced yet a noth er
kind of agent group: the car-park. Wh ereas th e form er was a cooperation among pee rs, whi ch lII erely
adheres to negotiation processes, the latter was based on a hi erarchi cal (allthoritarian) organi"at.ioll o f
agents that is based on orders a
The pros and cons of authority leve ls a re one a.<;pect of t.hat exalllJll e that. will no \. he st.l'cssl'd
here since it depends on th e app li cation at hand. A morp genmal aspect. is the way how hi('l' cU'c hi ca l
grouping allows for hiding the details of group organizat ion. A cli e nt 1.0 the grollp need no t <'v(' n kn ow
that he is actually interacting with a group. Furt.h erlil o re, aut.horitarian group organi"at.io n red uct,s
communication overhead between group memb ers and promises timely a nd co nsiste nt helmvi o l' of 1.11<'
group. In particular pred ete rmin ed group configurations that art' 1I0t. likely to be r('co lifiguJ'{,d alld t.hat.
operate mostly on standard sit.uations (e.g. thl' t.raffi c- light.s) an' calldid a t.('s fo r aut.llorit.ariall group
organ ization.
3Note that the choice of describing traffic-lights as peers and parking-lots as subordinates o f a car- park agent is onl.Y
for ill ustrating some of the different options in the o rgani 'Lat ion of agents. There is J\O rcaso n n o t tu introduce a c rossroadagent that gives orders to its subordinate traffic-lights or to organize a car-park based o n peer-to-peer coope rati o n o f
parking lots.
12
Chapter 4
Research Projects in the Field of
Traffic Control
In the past a variety of traffic control systems have bee n developed and install ed that str ive to improve
traffic situations with respect to one o r more of th e following general issues:
Security - E .g . notification of road users of weathe r a nd street condit ions ahead, improvement of
vehicl e technology.
Flow - E.g . anticipation of jams, coping with increase in traffi c vo lum e in general.
Ecological damage - E.g. improvement of effici ency of drive-t rain technology, homogeneo us traffic
flow, avoidance of unn ecessary (d e- ) tou rs, promoti o n o f th e use of pu b li c transportation systems.
Any traffic control system is concerned with a co ll ec tion of th ese issu es, but th eir deve lopers we ight
th em differently :
The major goal of the older systems is to cope with a lm os t unlimited increase in traffi c volllm e and
to enfo rce security for these volumes of private traffic by means of road co nstrll ction .
Emphasis has sh ifted in th e rece nt years. Sec urity issll es have beco m e in creas in g ly import.ant ill th e
publi c opinion, even though acceptance of the necessary steps, s ll ch as speed limits, is st ill no t. ve ry high .
The eco logical consequences of priva t.e ma'lS transportation have become publi cly no ticed r ~ce lltly , but
yet on ly a minority is willing to take th e appropriate steps .
This ongoing sh ift has co nsequ e nces for th e development. of fllture traffic systems. Since secu rity and
ecological issu es are considered more imp ortant. now , com p let.e ly d iffe re nt. syst.ems wi II em e rge; some of
their typical character isti cs a re [6]:
• A general shift from private to publi c transp01·tation means will occu r. Beg innin g with th e (short
distance ) urban traffic systems acceptance of publi c tra nsp o rtation m eans will in crease a lso for
long distances.
• As opposed to the o ld er systems that cope with road users as an anonymous mass , future systems
will be much more concerned with the individual needs of customers. Th erefore, th e integration
of private and public transportation m eans has to be enforced (e.g. park-and-rid e systems) a lo ng
with a general shift towards publi c systems . Th ese will ha ve to offer se rvi ces customized to th e
individual needs of each user.
• Future traffic systems will be information processing and transmission systems. As was pointed out
in the previous chapters, intelligent networking and coope rative inte raction amo ng th e co mpon ents
of the traffic systems will be crucial for th e performance o f th ese systems.
As was pointed out in th e previous chapters , th e MAS approa.ch t.o t.r a ffi c co ntrol exhibits t.h ese very
characteristics.
Traffic control syste ms a re emb edd ed in a network o f interes ts. FIIl.lIn' d(' v(' lo plll(' lIt.s will
for th em in order to be publicly accepted:
13
"(lV( '
t.o (I("("Ol illt.
Social interests - Concf'rn i ng hllsi TH'SS as IV(' II as spar(' I.i ITIt' acl.i vi I.il's .
Economical int erests - Such as unrestri cted pu rs uan c(' of
O llt' 's
pro f('ss io n .
Ecological interests - A voidance of exhausts and no ise, savi ng reso u rces .
Aesthetical interests - Preserving th e quality of resid e ntial areas, parks etc.
The hypothesis is that all these interests can be reco ncil ed in th e futur e by e mpl oy ing coopemtively
working, interactive systems. He re , MAS techn o logy provid es a promising prospective.
Since a compre hensive treatise goes beyond th e scope o f this paper, only two o f th e co nte mpo rary
(G e rman and European) research proj ects are sketched he re. Namely th e proj ects I' 110 M ETII E US and
LISB will be described , re prese nting ve hi cular traffi c co ntro l proj ects in general.
4.1
PROMETHEUS
Th e proj ect PROM ET II EUS ( PRO g raMlTlI' fo r <I n Ellro pl'a ll Trilfli e willi Hi g ll<'s l Efri ei" ll e,Y a lld
Unprecede nced S afety) [4] [5] is a j o int. [('search dfort. of 1.11<' \Vl'sl.l' rll - I·: lIropl'a,II illlt.Olllohil. , illdll st. ri. 's
a nd research institutes. It is o ne o f the la rgest EUltEI";!\ proj ce t.s .
The main objectives are improv ing safety and rcdll cin g l'co log ical dkel.s o f 1.11<' t.r a nsp or l. SYSt.l'IIIS .
PROMETHEUS reli es m ost ly o n improvf' lIl e nt o f vehicle technology. Ikv(' lo plTl<'nt. o f illt.(' lli g( 'nt. v( 'hi el('s
is pursued, but min o r e mphasis is puI. o n improv('men l. o f 1.11(' infr as t.rll ct. llrt' . 'I'll(' 0\'(' 1',,11 proj('c l go;ds
are a sequence of steps:
I. cars th at g ive info rmat.i o n ,
2. cars that e mit warnings,
3. cars that give instructi o ns,
4 . cars that co rrec t th e d ri ve l' 's actions,
5. cars that steer th e mselves.
PROM ETII EUS is a compound of seven research art'(l.s that a re assign('d to tIl(' pa rtn c rs. Ind II st. rial
research e ncompasses th e fo llowing three a reas:
PRO-ROAD Developm e nt o f comm llni cat io n systems linking infrastr ll ct llre and o ll - hoa.rd COl llp"t(' rS
that a ll ow fo r dece ntr a lized traffi c co ntro l.
PRO-NET Develo pm e nt. o f a co mmlilli cat.i o n sysI.f'1l'I linkin g v"'li clt's in o rd f' r to iner('as(' 1.1 1<' drivn 's
pe rcep ti o n range and to g ll a ra nl.('(' safl' a nd ha rm o nizl'd t.raffi c fl o w.
PRO-CAR De velo pm e nt of an inte lli gent. o n- hoar d SYSt.CIlI thaI. info rlli s a nd act. iv(' ly sllpport.s 1IJ('
drive r .
Basi c research, done a t unive rs iti es , e nco mp asses th e fo ll ow ing fOllr arCets:
PRO-GEN Conceiving traffi c scenarios that a ll o w a nalys is and evaill at io n o f th e systems developed .
PRO-COM Dcve lo pm c nt of s tand a rd s a nd prot.oco ls that e nah le co mmuni cati on arnong o n-hoard
co mpute rs o f vehicles a nd between vehicles a nd the infras tru cture.
PRO-CHIP Impl e m e ntati o n o f th e req llired co mpute r hardware .
PRO-ART De ve lopm e nt of pro cedures and a lgo rithm s that allow IItiliz'a ti o n o f a rtifi cia l intelli gence
in futur e traffic systems.
Th e common prop e rty o f all research d o ne in project PROMf,TIIEUS aims at improv ing private
transportation means . Integration of publi c and private m ea ns is o f minor conce rn . In parti c ul a r
PROMETHEUS does not pursue redu ction of private traffi c vo lum es.
14
4.2
LISB
LlSB (Le it, und Info rmati o ll s Sysl.C' 11I DC' riin) [.ell is a fi. ,lei Sl.lleiy CCll'l'i " ei 0 111. ill Ikl' lin . 'I'h " Pl'o t.o t.ypi ('al
system is a navigational aid that pursues traffi c co ntro l tasks hy individually g uidin g anonYiliOUS road
users. A similar system, call ed AUTOGUIDE , will he in stallC'd in Lo nd o n .
LISB is comprised of stat ionary sender/receiver units that are dist ri buted a ll o vc r (.he t o wn. Ve hi c les
continuous ly transmit sensory data such as th e time required to m ove al o ng a road t o th e systeill. LISB
samples the data and updates its centralized database. Eve ry 5 to 10m i nu t cs th e lates(. in fOrillati o n
about the current traffi c situat ion is broadcas t .
Ve hicles continuously listen to th ese broad casts. Th e ir o n-b oard navigati o n co mpute r filt e rs a nd
processes the info rmations with res pec t to th e ve hicl e's d es tination . It d e rives gu idill g hints and prese ll ts
the m to the driver by m eans o f a display and natural languagc utte rances.
Based on the ce ntra li zed pro cess in g o f up- to- date tr a ffi c vo lum e data individu a l guidan cc can be
provided with res pec t to th e current traffi c s itu ations. Notc t hat a ll road-u se rs stay anO llYIlI OI IS. LI SB
is based on a ce ntral database whi ch is co n(.inll o us ly upd il(.('c! hy (.h e in co millg vf' hiclC' da(.a and whi ch
co ntinuously gene rates th e latest traf fic g uid a nce info rmat.ion . 1.'lIrtill'J'lll o J'( " I.his dat.;l.h asc' all o ws 1,0 <kal
with:
• traffi c manage m e nt according to g ivc n po li (' ies,
• traffi c li g ht co ntro l,
• radio traffi c serv ices,
• pa rk-and-rid e systems, pa rkin g s pa('e o('(' upan ('y ('0 111.1'0 1,
• ro ute and travel plannin g ,
• co mm e rcial fl eet man agc mt' lll.,
• supe rvi sion o f dangC'rou s goods t.r a nsporl.a l.i o n,
• and tra ffi c pl a llnin g.
Proj ec t LISB a lso e nco mp asses investigati o ns co ll ce rning t.h c acceptance o f s ll (' h a SYS I.CIII hy till'
use rs. It has re vealed that on routes whi ch th c ro a d user d oes no t kn o w in advallce, acc<'ptan('c o f 1.11<'
guid ing informations is ve ry high , on known rout cs it is high . On 53 pe rce nt o f th e ro utes tak e n by
private persons guiding hints we re a lways o beycd . On 41 pe rce nt o f ro utcs taken hy bllsin( ~ss vehic les
guiding hints we re a lw ays o beyed .
15
Chapter 5
Conclusion
Th e exampl es in th e first thrf'e chapt.e rs haw rC'vealed that. t.Ilt' MAS paradi-gm , when e mployed in
th e urban traffic scenario, leads to an highly integ rated syste m that a ll ows to acco unt fo r virtually a ll
relevant aspects of traffic co ntrol.
Furth ermore, as Chapter 4 has pointed out, th e adoption of th e M AS paradigm d oes no t enta il negl ec t
of other approaches to traffi c control problem s; it rath er a ll ows to integ ra te th em . Th e rat io nalizati ons
presented in the first three chapters have been presented with o ut refe rring to th e state o f th e a rt in
traffic control research proj ects . After loo king at th e projects prese nted in C hapte r 4 , it turn ed o ut
that the ' MAS view ' on traffi c co ntrol is an obviously na tura l one th a t is not o nly co mp at ibl e but even
complem entary to these proj ects.
Therefore, we may conclude that th e MAS approach to th e UTS is a promising way to organize
a broad vari ety of already existing and of up com ing technologi es according to o ne commo n paradigm .
MAS research is able to make viabl e contributions in th e do m a in s o f co mmuni cat io n , coo perat ion,
distributed information processing a nd co ntro l.
Acknowledgements
Th e concepts and id eas presented in thi s paper were deve lo ped in the D PK I Proj ec t KI K- TEA M WA RE
and in th e Esprit II Proj ect No . 5362 , IMAGINE. Prototyp ical impl e me ntations o f th e UTS , as described in an associated pape r [9], were pa rt. o f t.h e co nce pt.lIal prot.o t,yping ph as(' o f 1M AC I N I'; a nd
se rved to support the rat.i o nalizati o ns presC' ntN I h{~ r ('.
Thanks to th e m emb ers o f KIK-TEAMWARE a nd Il a ns II allgf' IH'd C' I' , wh o co nt,l'ihIILf'd to til{' d('v{'l opment of th e urban traffi c scenarios thro ugh fruitflll di sc uss io ns .
16
Appendix A
Towards an Implementation
This appe ndix o utlin es how the age nts o f th e urb a n tra ffi c scellario call 1)(, sil ilpliri ed co li s id e rably alld
can be mod e led by means of the concepts o f multi-age nt sys te m s technol ogy. In contras t 1.0 t he ilifo rill a l
examples in the main part o f this re port , a m o re techni cal desc rip t io n of a basic se t o f age nt.s is pr< ~scnt('d
here .
In o rde r to keep the examp le simp le, on ly a res tri c ted set o f basi c types o f agents will be illtrodu ced .
Compared to real world traffic scenari os th e s imul at io n will he be cons id e ra bly less co l1lpl e x . So , in stead
of striving for a comp re hens ive s imulati o n o f reality, e mphasi s will be put 0 11 tb e app li cability o f th e
major multi-agent system asp ects to th e UTS d o main . Co rres po ndingly, th e fo ll ow ill g m o del is bi-lsed
o n the rat io nalizati ons o f th e a uth o r , and not on f' xhallstive nat. llre illvestigat.ion .
Three types of non-mobil e agents a re used to m o de l a c ity map, i.e . th e nOll- m o bil e parts of th e
sce nario : STREETS l , CROSSROADS (fo ur s tree ts joi llin g) a nd T- J UNCTIO NS (t hr ee Htfl 'l' t s j o illillg). Not.,
that, as opposed to its usual meaning, th e te rm st reet d e ll o t.es Il o thill g rll o re t ha ll a pl a in co llil ect io ll
between adjacent crossroads and/o r t-jun ct io ns . Clto SS ltoAD S <llld T-.Il IN CTIONS IIl o d pl t.11t' CO IlIH'C ti o ll
of STREETS with res pec t to ' flow ' o f mobil e age nts thro ug h th e lll il.lld a t th(' sallH ' tilil" illclud p tilt'
functionality of th e tram c- li ghts, i. e . o f fl ow co ntro l.
Mobil e agents are re prese nted by the gellcra l agP lit typt' VE III C: L~; . (Sillc(' tiris papn d p,;cr ih.!,; a fir,;"
app roach to a MAS imple m e ntation o f the UTS, ped es trian s arc no t. yet. mod e led . ) Tir es!' agents ,Lrc t.h e
on ly auto motive parts in th e UTS mod e l. Th e ir pllrp ose is t.o II IOVP a.lo llg ST IU·; F;TS, pass Clto SS IW ADS
a nd T-JUNCTIONS and th e reby bring t.o life t.h e sinlill at. io n ."
A.I
Street Agents
A STREET agent mod e ls th e space between consecutive CRO SS ROADS o r T- .JUN CTION S. To keep th e
e xamples s imple, on ly streets with a s in g le lane fo r each direc t.i o n a re co nsid e red. Deri niti o ll I illustra t.es
the majo r properties o f a STREET agent.
A STREET is of a given length (stree t/ength) . The m ean le ngth of a VEIlICLE:' includin g a minimal
distance to the next VEHICLE, is call ed car/englh . Gased o n th ese valu es th e m ax imum capa czly o f one
lane o f the STREET can be co mputed as sh o wn in Definiti o n I . Note that, in reality , th e capac ity de pe nds
o n the speeds at which th e ve hicl es a re moving s in ce th e di s tances be twee n (human co ntroll ed) ve hi cles
must in crease with speed. So the capacity o f a st ree t is at its maximum wh e n a ll ve hicl es stand st ill
and decreases as ve hicl es increase th e ir speed . T o keep th e e xample s impl e, the capacity is treated as a
constant value.
I Note the typ e face o f th e wo rd STREET . When eve r a p a rti c ular type or agent o r tl.. e /lI ode l is rcf"rred, small cap it a l
let t ers are u sed. To den o t e th e general m eaning o f th e word norma l typdace is used.
21n the future this m o d e l will be ex t e nd ed in o rd e r t o in c lu de group agents, e.g. het.t!rogent"" 's groups cO lllpri sed
plus CROSSRO A DS and T-JUNCTIONS and h o m oge n eo us groups co mpri sed lI r I 'A"" I NG-L()TS which ill tu .... rll .... ,
C AR-PARKS . Furthermore, a sort o r reg is ter agent is n"cessary in o rd e r 1.0 mod,,1 the pro c"ss of m ob il e agents e nte ring u r
ieavillg the scene.
of
STREETS
17
Deft ni tions:
let carl ength be the mean length of a VEHI CLE;
let s tr ee tlength be th e length of th e STREET;
the STREET has a maximum capa. city for each la ne:
capa city := l s tr ee ti ength -;- carl enythJ
~-------
th e fl ow in a la ne can not exceed th e capacity:
Definiti o n I : Pro pe rti es o f a ST REET
The re for e, a STREET can be re prese nted s imply a s a pa ir o f qu e ues. 3 Eac h que ue is capa bl e o f ho lding
a certain numbe r of VEHICLES . The maximum qu e ue le ng th is capa city . Th e fun cti o na lity o f each q ue ue
is to acce pt as many VEHICLES as possibl e fr o m its input-s id e. On th e o utpu t-s ide th e dr a inin g o f
VEHICLES is controlled by th e ne xt traffi c- light . As lo ng as thi s tra ffi c- li g ht (o r wh a te ve r e lse ) in te rru p ts
th e draining away, the qu e ue will not b e a bl e t o acce pt m o re VEHI CLES th a n up t o its capac ity lirnit. 4
A.2
Crossroads and T-J unction Agents
Streets have bee n mode led in t he pre vi o us secti o n as bidirectio na l buffe rs. Th ey e xhibit a ra th e r primitive
be havi o r . Cross ro ads and t-junctions in co njun cti o n with th e ir assoc ia ted tr a ffi c-li g hts pro vid e a ri cher
fun ctionality. In pa rti cular , th ese strive t o inte lli ge ntly co ntro l th e tra ffi c fl ow . As o pp osed t o th e
STREETS , tra ffi c-lights and CROSSROAD S o r T - J UNCT ION S a re ac tive age nts in th e m o d e l. T o kee p t he
m o d e l simpl e, CROSSROAD S o r T- JUN CTIO NS a nd th e ir sets o f assoc ia ted tra ffi c-li g ht.s a re m o d e led as a
s in g le age nt .
A.2.1
Crossroads Agent
Definition 2 ske t ches th e m a in pro pe rti es o f a CRO SS ROAD S age nt. co nce rnin g th e asp (~ c t s o f t ra ffi c fl o w .
Conforming with th e simple m o d e l o f s tree ts g ive n a bo ve, in te rsec tin g s tree ts d o no t fo rk o ff ri g ht- turn
and/or le ft-turn la nes. Thi s restri cti o n a ll o ws t o d o with o ut. tr a ffi c- li g hts t.h a t s ho w a r ro ws fo r t he
diffe re nt direc ti o ns o f tra ffi c fl ow a nd s implifi es li g ht sequ e nce co ntro l co ns id e rably .
Eve n in thi s s implifi ed c ross roads m o d e l, li g h t sequ e nces o f th e illdividu a l tra ffi c- lig hts a re s t ro ng ly
inte rd e p e nde nt. Oppos ite directio ns a lw ays s wi tch in sy nchro ny. Th a t is, flow_a _in a nd flow _b_in a re
co n t ro ll ed by e xactly th e sam e sequ e ncp. TIlt" sanlP ho ld s fo r flow _c _in a nd flow _d _in . Furth e rm o re
these two seque n ces a re co mpl e m e nta ry t o each o th e r: whil e th e a an d b li g hts s ho w g reen th e c a nd d
lights must sh o w re d a nd vi ce ve rse .
The m a in fun cti o nality o f the CRO SS ROAD S is impl e m e nted by its assoc ia ted se t o f tra ffi c- li g hts.
Th e ir task is to control the flow of traffi c so th a t all directi o ns a re se rved equ a lly . Based o n t he s im p le
m o d el ske t ched above , Algorithm 1 d es crib es th e beh a vi o r o f a se t o f tra ffi c- lights a t a CRO SS RO ADS.
The con s tant value default, whi ch is arbitr a rily set t o 15 seco nd s in Algo rithm 1, d e te rmin es th e
st a ndard le ngth of red and green phases. As lo ng a '3 no s ignifi cant diffe re nces in tra ffi c fl o w vo lum es
a re d e tec t ed, th e traffi c-lights adh ere t o thi s d e fa ult va lu e. Th e co ns t a nt threshold d et e rmines ho w
si g nifi cant th e diffe re nces in tra ffi c fl o w vo lum es mu s t be in o rd e r to d e vi a t e fr o m d e fa ult timin g.
Th e algo rithm is co mprised o f a n infinite loop . Each ite rat io n starts wi t h gath e rin g up- t o- d a t e
informatio n ab o ut th e c urre nt tra ffi c vo lum es. Th a t is, t he ac tu a l valu es o f flow _a _in ... flow_d _in
have to be d e t e rmin ed . s Based o n th ese va lu es th e diffe re nce in fl o w vo lum es (diff) is calclli a t ed . As
3Note that in ord er to keep the example simpl e. st reets have onl y on" Ia nI' for ('a.. h dir('c ti on; "0 kfl.-tlll'l1 or ri ghl -tur"
lanes and no one- way streets are considered .
1The simplicity of this model is intentional. It is obv ious that a model of a rl'altraffi r s(,e na ri o will b .. far mort' ('o lll pl('x
with respect to the mathemati cal model descri bing Rows a nd capacit ies. In part icular . the co mplex interd ependencies
between consecutive streets and crossroads (the net-effec ts) would be of great si gnificance in a more realisti c model.
5Flows are non-negative integer values.
18
- -
De finitions :
th e s um o rall input fl o ws and output flows lIlus t be
eq ual to ze ro :
I
-+-
- -
d
L(JlowJI _il! - JloI/IJl j) l/.i) = 0 ;
fl ow_c in
Definition '2: l'rop('r t.i ('s o f a
CltoSSROAf)S
long as diff does not e xceed threshold , th e traffi c- li g ht.s adhere to the (!Pfa llit ti/llin~. Ot.herwise,
the timing is adjusted by prol o nging the g ree n phase fo r the high volllnl<'s clirectioll{s). Pro lo ll gati o ll is
limite d to at most three tim es the default 6
A.2.2
T-Junction Agent
A n important variant o f a C RO SS ROA OS is the t-shapeci j II nct.i o ll o f o nly th ree roads. l)c[i n i ti o ll :\ sketches
the major properti es o f a T-JUNCTION age nt . All re nlarks co nce rning a C RO SS ROAf) S are va.lid fo r t.hl'
T-JUNCTION agent as we ll.
In the T-JUNCTION mod e l, light seqllences of the inciividllaltrafJi c- lights are strollgly illt(' rdq)(!lId c lIl..
Opposite directions always s witch in synchrollY. That is , flow _a _in and flow _b _in arl' ("() lItro ll l'd hy
e xact ly the same sequence. Thi s seq ue nce and the seqll c ll ce co lltro llillg flow _c in arc' cO lllpl(' JIH'lItar y t.o
each ot he r: whil e the a and b lights s ho w g ree ll the c li g hts JlllISt show J"('d a lld vict' V('fS( ' . AI~oritlllll '2 is
s imilar to the previous algorithm. It ilill st rates the adjllst lll!' nt. o f li ~ ht. Sl'q ll(' II C('''; a t. !.II<' T-.IUN(,TIO dl\('
to the traffic volum es. Note that the d irect. io lls a and hare g iv(' 11 prl' f( ' r<'lIc(' ove r c a";"; lllllill~ t.Il a t IIsllall y
the main tra ffi c volumes are flow_a _in and/or flow _b _in . Th e refo re, if traffic volllilic flow _c in raises
above the given threshold its green phase may be prolongat.ed lip t.o fiv (' t.im es it.s (kfallit. a,.; o pp o,,;('d
to at most three tim es fo r the directions a a nd b.
In a MAS impl e m e ntati o n o f th e traffic scenario each individllal jllnction o r c ross road will be tllned
by adjusting th e de fault tinling of light seqllences individllally to th e typical traffi c voillmes. TlIning
may be don e a pri o ri by th e impl e m en to r o r t.hrough a co nt.inll o ll s learning process.
A.2.3
Computing Flow Volumes
During the green phases a certain numb e r of VEHICLES pass th e traffi c- light. This is limited by the le ngth
of the green phase and may be furth e r red uced if the draining away of ~EIIICL ES is obst ru cted. The
actual numbe r of VEHICLES that passed a traffi c- light during the last green phase has to be deterrnined
in order to compute th e (n ex t set of) up-to-d ate va lu es fo r flow_a_in ... flow _d _in . In th e a lgo rithms
6 All values are chosen arbitrari ly. In an impl e m e ntatio n o f th e UTS s imulati o n th ey have to be adjuster! appropriately
fo r each individual agent.
I!J
/* Let a_b_green be the length of the green phase for flow_a_in
/* and flow_b_in. Let c_d_green be the length of the green
/* phase for flow_c_in and flow_d_in. a_b_red and c_d_red are
/* the respective red phases.
threshold := 10 /* Minimal flow difference that leads to
*/
/* changes of the default length of phases.*/
default := 15
/* Default length of a red or green phase. */
ASSERT (c_d_red
a_b_green) /* Red and green phases must */
ASSERT (a_b_red == c_d_green) /* be kept complementary.
*/
LOOP
/* Determine current flows . */
diff := (flow_a_in + flow_b_in ) - (flow_c_in + flow_d_in)
IF (diff > threshold) THEN
a_b_green += MAX (diff, 3*default)
c_d_green := default
ELSEIF (diff < (-threshold» THEN
c_d_green += MAX (ABS(diff), 3*default)
a_b_green
default
ELSE
a_b_green
default
ENDIF
ENDLOOP
*/
*/
*/
*/
Algorithm I: Adjustm e nt of Light Sequences at a CROSSROAD S
- - -
T
- - -
De finitions :
the sum of all inpllt flows and Oll tpllt flows must be
eq ual to zero:
I
II: I
a T - .Jl ' N(,TJON ha.s 110 C(/,7111ct l y .
r
now_cin
Definition :3: Prop e rti es of aT-JUNCTION
given above this computation is indi cated by th e co mm ent ' dete rmin e c urre nt nows '. How this can be
done is investigated in the fo llowing.
Let flow....a_in be the number of VEHICLES that compr ise th e current traffic volum e at a CROSSROADS
(cf. Definition 2). These VEHICLES , wh e n on a green li ght, wi ll distribute to the output nows flow _b_out
... flow_d_out as long as no obstruct ion arises. Since accidents are ignored he re, this req uires only that
the output lanes must be at less than capacity. Th e refor e, before a mobi le agent e nte rs th e c rossroads
it has to check that the lane it is heading for has e nough fr ee space left. Not on ly does this conform to
the traffic regu lations, it is a lso a req uire m e nt a ri sing from th e definition of the mod e l whi ch states that
CROSSROADS and T-JUNCTIONS have no capacity.
To determine the latest Aow values req uires counting th e VEHICLES that left the CROSSROADS or
T-JUNCT ION through the out Aows during t.he last. g ree n phase .
20
/* Let a_b_green be the length of the green phase for flow_a_in
*/
/* and flow_b_in . Let c_green be the length of the green phase
*/
/* for flow_c_in . a b red and c_red are the respective red phases . */
threshold := 15
/* Minimal flow difference that leads to
*/
/* changes of the default length of phases .
*/
default_a_b := 15
/* Default length of green phase for a and b . */
default_c
:= 10
/* Default length of green phase for c.
*/
ASSERT (a_b_green == c_red) /* Red and green · phases must be kept */
ASSERT (a_b_red == c_green) /* complementary .
*/
LOOP
/* Determine current flows , */
diff : = «flow_a_in + flow_b_in) / 2) - flow _c_i n
IF (diff > threshold) THEN
a_b_green += MAX (diff, 3*default_a_b)
c_green := default_c
ELSEIF (diff < (-threshold)) THEN
c_green += MAX (ABS(diff). 5*default_c)
a_b_green .- default a b
ELSE
a_b_green
default a b
c_green
default c
ENDIF
ENDLOOP
Algorithm 2: Adjustm e nt of Light Seq uences at aT- J UNCT IO N
For a complete light sequence at a CROSSROADS th e comp utat ions a rc as follows: 7
+ JIOllU;_ol/.l" + IloWJLoll.i.,,)
(fI01UJLU11.1b + JI ()lIU'Jm1b + JII)H u L()II/./,)
(flulIu uml + Iioll'_h_u/i. / + Ilull u Loul ,. )
(fIO'lU_(LOuld + IlolldLould + Jlow _cuul ,tl
flow_a_in' := Jlow_a_in - (flow _b_oul"
Jlow_b_in' := Jlow_Lin Jlow_cin' := JIU1U_cin Jluw_d_in' := JI01U_(Lill -
r
r
And the ove ra ll out flow i (i E {a . . . d}) during a comp lct.e' li ght. scqucncI' is thl'
flows or iginating from all direc t ions but i:
Sl l " l
of' a ll part.ial
Jlow_i_oul' := "d
_ ~ . fl olll_i_01I.I 11
L V _ Q , IIr-l
For a comp lete light sequence at a T-JUNCT IO N computat ions a re sim il a r :
fl ow_a_in' := fl ow_a_in - (flow_b_oul a
+
flow_b_in' := fl ow_b_in - (flow_a_outb
+ fl ow_c_ottlb)
fl ow_c_in' := flow_cin - (flow_a_01tl c
+ flow_b_01tl c )
fl ow_coul a )
The ove ra ll out flow i (i E {a ... c}) during a comp let.e li ght sequ e nce is t.he sum of a ll partial flows
originating from a ll directions b ut i:
Jlow_i_oul' :=
"c
~ l. flow_i_oul ll
L/I=a ,Jl r
These formulae have to be in tegrated into the respective a lgo ri thms (see above) in orde r to comp lete
the algorit hmi c description of the behavior of CROSSROADS and T-JUNCTION agents .
7The indices of the out flows indicate th e sOllrce. For examp le
via lane a coming from b.
C ROSSROADS
LI
j{ rl1lUL,mt/,
is the fIIl/llb"r of
V f-: III C LES
\.ha\. leave t il<'
A.3
Vehicle Agents
The main action of mobile agents in the UTS is to move around in the scenario. Moving along a street
is almpst completely mode led by the STREET lanes which organize VEHICLES in que ues. The much more
inte resting event, from the viewpoint of simulating an UTS, is a VEHICLE passing a traffic-light. In the
following , the model of mobile agents will fo cus o n this issue.
size
I~
.---ve h-i-c1e ----,'
~
turnJeft
straighLah ead
turn_right
Definitions:
the actual length of a VEHICLE is an integral multiple of the
basic unit car leng th :
size = n * car/ength
the direction of th e VEHI CLE 's next move is :
dir ection E {turn _le ft , turn_right, s traighLah ead }
De finiti on 4: Properties o f a VEHICLE
De finition 4 d ep icts the major pro pe rti es o f a VEHICLE agent. Por queuing up VEHICLES a lo ng a lalle
the le ngth o f each VEHICLE is imp o rt. a nt . '1'0 facilitate modeling it. will bl' ass um ed that a ll VE HI CLES
are e ithe r o f eq ual le ngth (cf. De finiti o n I : car' /ength) o r an illteg ra l Illuitipl e thereof. A VEIIICLI:: must
com muni cate its size to its host STREET ill o rdf' r to enable the ST It I:: ~; T to cornp u(,c t he Clirre ll t load.
1* Let SELF be the identification of the mobile agent,
*1
1* SIZE its length,S, 51, 52 identifications of streets *1
1* and T the identification of a traffic light .
*/
1* entering a street 5 : *1
WHILE NOT capacity_available (5, SIZE) DO
1* do nothing, wait until street is free
ENDWHILE
register (5, SELF, SIZE)
*1
1* leaving a street 5 : *1
unregister (5, SELF, SIZE)
1*
1*
1*
1*
1*
1*
SELF is the next vehicle on 51 to pass T wanting to *1
enter street 52. 52 is determined by calling step() *1
which tells the destination street of the next step *1
in the plan . So 52 is the street forking off at T
*/
which is reachable from 51 when making the 'next()' *1
step of the plan .
*/
52 : = step(T, 51, next())
WHILE green_phase(T, 51) DO
IF capacity_available (S2, SIZE) THEN
unregister (51, SELF, SIZE)
register (52, SELF, SIZE)
tell (T, Sl, S2)
EXIT_WHILE
ELSE
1* do not move, i.e. block the lane */
ENDIF
ENDWHILE
Algorithm 3: Act io ns of a VEHICLE Agent
Anothe r important prop e rty is th e direction the VEHICLE wants to take at the next CROS SROADS o r
22
T-JUNCTION. We assume that mobile agents have their give n plans det.ermining their rout.e. The plans
may be generated in advance or may evolve dynami cally. Guid ed by its plan , th e VEHICLE finds its way
through a t.own. An enumeration fun ction next (c.r. Algorit.hm 3) maps t.he plan into it.s single st.eps.
Upon each call it ret.urns the direction of th e next step in turn. So, for the mobile agent to find its
way, it ' has to call next at each CROSSROADS or T-JUNCTION and, when given way, turn to th e direc tion
d etermined by next.
Algorithm 3 lists three main fun ct ions of a mobil e agent. Th e first one is called whenever the agent
wants to enter a street. It th e n tri es to registe r with th e STREET agent S by telling its id e ntification
SELF and its SIZE. If the STREET agent is used up to its capacity (fill ed with VEHICLES) th e VEHICLE is
caused to wait until enough space becomes availabl e.
The complementary function is to leave a STREET whi ch m eans the leaving VEHICLE un-registers
with the STREET agent and fr ees the space it had occupied.
The most complex action sequence models the passing of a traffic-light which is a combination of
leaving one STREET (Sl) and entering another (S2). This action sequence is initially triggered when
the VEHICLE becom es the next one to pass the traffic-light T (i .e. is the first one in th e SI queue) and
stays active during th e green phase for S 1. To de te rmin e whi ch of th e t.wo or three STREETS reachable
from Sl will be e nte red next , the VEHICLE 's plan has to be int.e rrogated. Applying th e function next
to the route plan t.e lls whi ch d irect ion to t a ke. So , being in street SI at. traffic- light T and knowing t.he
direction of the ne xt. st.ep suffices to det.erm ine which STREET to e nte r next. Let this STREET be S2.
As describ ed above, this succeeds only if e nough space is available at. S2. Th e n th e VEIIICLE leaves SI ,
e nte rs S2 and notifies the traffi c- light whi ch way it took. Oth e rwise th e VEIIICLE blocks its lan e until
S2 has e nough fr ee capacit.y. Recall that. CRO SS ROAD S o r T-JUNCTIONS have no capacity .
Explicitly notifying t.h e traffic-light. is req uired , since this e nabl es it to count in and out. flows and
compute the current flows at th e beginning o f th e ne xt. light. sequ e nce (cr. Section A.2.3) .
AA
Conclusion
Thus we have seen how t.h e processes of the various agents involved in th e UTS may be mod ell ed
inde p e nd e ntly of each ot.her, yet. int.e ract coope ratively t.o gllarant.ee a n effi cie nt. and smoot.h flow of
traffic .
The first. protot.ypi cal urban t.raffi c scenarios have a lready heel! impl e m e nted and no t only s how
feas ibility of our approaches but. promises t.o co mpl ete ly fllifill o llr ex pec tat. io ns [9] .
23
Bibliography
[1] Scie ntific Ame ri can , Special Issu e: Co m771U7t! Ca tlOl/l) , ('(m /fllL/ el'l) a1ld Nc lw01'l..:s , Scpt. 1!)9 1.
[2] A. H . Bond, L. Gasser : Readings in Distribut ed A rtificia l Int ellig ence, Mo rgan 1\ a ll flltall PII hi is itcrs ,
San Mateo , CA., 1988.
[3] C. Rich , R . C. Wate rs (eds.): Artificzal Int ellig ence alld Sof/ wll1'e 1:;//,ql1l ee1'l1lg, Mo rgall I\a'lf", a l'
Publish ers , San Mateo, C A ., 198(j.
[4] U. Franke: PROM ET/I EUS: Wlssensbasle1'le Systemc f1'OeJJlI Cll neue l) c1'Sl'ekil1l en 11I! ,,,'tmss cnverkehr. in : W . Brau e r , C. Frcs ka (cos.): Wissf' nshas ir>rt.(' SYSt'('llI(" :1. 11It.(' rnati o ll a lf' r (; I- I\ o llgrf'ss
Miin che n, Springer Ve rlag , 1989, pp. ;!(j3-:I7G.
[5] Forschungsgese llschaft fu e r Straf3en - lind Vc rk c hrs w('se n , I~ (i lll : Vcrl.:ehl·s bermJIlLssulI,q, l~ o ll ()( PliulIl ,
25 . Januar , 1990 , Bonn .
[6] H . H . Topp (II rsg .): Verkehr aktu ell: CA TS Compu ter-A lded Traffi c SY!Jl e1lls Vorlrags/'('i II(' Wi 11 t e rsem est e r 1990/91, Fachge bi et Ve rk e hrswese n , Unive rs ita t Ka isf'rs la lltc' rIl
[7] A. Lux, F. Bomarius, D . Ste in e r : A Mod el f or SU l'Po1'ling /lUIn (!1/. Co m.put er· Coollera llOn, AAAI
Workshop on Cooperation among Il ete roge neo ll s Inte lli ge nt SYStCIIlS, San .1 OS(" CA . .J Illy I tJ , I 99::!.
[8] D. Ste in e r , D . Ma hlin g, II . Ha uge nede r : /lu771an Comp lL/('1' Coo llem /we Wor-k , ill: P roccedi ll gs o f
the 10th Inte rnati o nal Wo rksh o p 0 11 Oi st. rihllt.ed ;\rt.ifi cial llll. (' lli g(' II C:(~, Ba lld era, T('xas, Ocl.. ::!:\-L7 ,
1990.
[9] F. Bomarius: Using th. e M ECCA Sys/(,1II lo
Me m o TM-92-07 , Septe mher I gg::!.
!111]/1(,1II(,7I/
IIl' iJ lI. lI '/'m.jJi(' ....; (·(' 1I1I.1'l ()S, ))1"1";1 T('chllical
DFKI
-BibliothekPF 2080
D-6750 Kaiserslautern
FRG
Deutsches
Forschungszentrum
fOr KOnstliche
Intelllgenz GmbH
DFKI Publikationen
DFKI Publications
Die folgenden DFKI Veroffentlichungen sowie
die aktuelle Liste von allen bisher erschienenen
Publikationen konnen von der oben angegebenen
Adresse bezogen werden.
Die Berichte werden. wenn nicht anders
gekennzeichnet. kostenlos abgegeben.
The following DFKI publications or the list of aU
publisched papers so far can be ordered from the
above address.
The reports are distributed free of charge except
if otherwise indicated.
DFKI Research Reports
RR-92-05
RR-91-33
Ansgar Bernardi. Christoph Klauck.
Ralf Legleitner. Michael Schulte. Rainer Stark:
Feature based Integration of CAD and CAPP
Franz Baader. Klaus Schulz :
Unification in the Union of Disjoint Equational
Theories: Combining Decision Procedures
33 pages
RR-91-34
Bernhard Nebel. Christer Backstrom :
On the Computational Complexity of Temporal
Projection and some related Problems
35 pages
19 pages
RR-92-06
Achim Schupetea: Main Topics of DAI: A Review
38 pages
RR-92-07
Michael Beetz:
Decision-theoretic Transformational Planning
22 pages
RR-91-35
Winfried Graf. Wolfgang MaajJ : Constraintbasierte Verarbeitung graphischen Wissens
14 Seiten
RR-92-08
Gabriele Merziger: Approaches to Abductive
Reasoning - An Overview 46 pages
RR-92-01
Werner Null : Unification in Monoidal Theories is
Solving Linear Equations over Semirings
57 pages
RR-92-02
Andreas Dengel. Rainer Bieisinger. Rainer Hoch.
Frank Hones. Frank Fein. Michael Malburg :
n ODA : The Paper Interface to ODA
RR-92-09
Winfried Graf. Markus A. Thies:
Perspektiven zur Kombination von
automatischem Animationsdesign und
planbasierter Hilfe
15 Seilen
RR-92-10
53 pages
M. Bauer: An Interval-based Temporal Logic in a
Multivalued Setting
RR-92-03
17 pages
Harold Boley:
Extended Logic-plus-Functional Programming
28 pages
RR-92-04
John Nerbonne: Feature-Based Lexicons:
An Example and a Comparison to DATR
15 pages
RR-92-11
Susane Biundo. Dietmar Dengler. Jana Koehler:
Deductive Planning and Plan Reuse in a
Command Language Environment
13 pages
RR-92-13
Markus A. Thies. Frank Berger:
Planbasierte graphische Hilfe in
objektorientierten BenutzungsoberfHlchen
13 Seilen
RR-92-14
Intelligent User Support in Graphical User
Interfaces:
1.
InCome: A System to Navigate through
Interactions and Plans
'Tlwmas Fehrle. Markus A. Thies
2. Plan-Based Graphical Help in ObjectOriented User Interfaces
Markus A. Thies. Frank Berger
22 pages
RR-92-1S
Win/ried Gra/: Constraint-Based Graphical
Layout of Multimodal Presentations
23 pages
RR-92-16
Jochen Heinsohn. Daniel Kudenko. Berhard
Nebel. Hans-Jurgen Pro/itlich: An Empirical
Analysis of Terminological Representation
Systems
38 pages
RR-92-17
Hassan Ai"t-Kaci. Andreas Podelski. Gert Smolka:
A Feature-based Constraint System for Logic
Programming with Entailment
23 pages
RR-92-18
John Nerbonne: Constraint-Based Semantics
21 pages
RR-92-19
Ralf Legleitner. Ansgar Bernardi.
Christoph Klauck: PIM: Planning In
Manufacturing using Skeletal Plans and Features
17 pages
RR-92-20
John Nerbonne: Representing Grammar. Meaning
and Knowledge
18 pages
RR-92-21
J6rg-Peter Mohren. Jurgen Muller
Representing Spatial Relations (Part II) -The
Geometrical Approach
25 pages
RR-92-22
J6rg Wurtz: Unifying Cycles
24 pages
RR-92-23
Gert Smolka. Ralf Treinen :
Records for Logic Programming
38 pages
RR-92-24
Gabriele Schmidt: Knowledge Acquisition from
Text in a Complex Domain
20 pages
RR-92-2S
Franz Schmallw/er. Ralf Bergmann. Otto Kuhn.
Gabriele Schmidt: Using integrated 1cnowledge
acquisition to prepare sophisticated expert plans
for their re-use in novel situations
12 pages
RR-92-26
Franz Schmallw/er. Tlwmas Reinartz.
Bidjan Tschaitschian : Intelligent documentation
as a catalyst for developing cooperative
knowledge-based systems
16 pages
RR-92-27
Franz Schmallw/er. J6rg Tlwben : The modelbased construction of a case-oriented expert
system
18 pages
RR-92-29
Zhaohur Wu. Ansgar Bernardi. Christoph Klauck:
Skeletel Plans Reuse: A Restricted Conceptual
Graph Classification Approach
13 pages
RR-92-30
Rolf Backo/en. Gert Smolka
A Complete and Recursive Feature Theory
32 pages
RR-92-31
Wolfgang Wahlster
Automatic Design of Multimodal Presentations
17 pages
RR-92-33
Franz Baader:
Unification Theory
22 pages
RR-92-34
Philipp Hanschke:
Terminological Reasoning and Partial Inductive
Definitions
23 pages
RR-92-3S
Manfred Meyer:
Using Hierarchical Constraint Satisfaction for
Lathe-Tool Selection in a CIM Environment
18 pages
RR-92-36
Franz Baader. Philipp Hanschke:
Extensions of Concept Languages for a
Mechanical Engineering Application
15 pages
RR-92-37
Philipp Hanschke: Specifying Role Interaction in
Concept Languages
26 pages
RR-92-38
Philipp Hanschke. Manfred Meyer:
An Alternative to 0-Subsumption Based on
Tenninological Reasoning
9 pages
RR-92-41
Andreas Lux: A Multi-Agent Approach towards
Group Scheduling
32 pages
RR-92-42
John Nerbonne :
A Feature-Based Syntax/Semantics Interface
19 pages
RR-92-43
Christoph Klauck. Jakob Mauss : A Heuristic
driven Parser for Attributed Node Labeled Graph
Grammars and its Application to Feature
Recognition in CIM
17 pages
RR-92-44
Thomas Rist. Elisabeth Andre: Incorporating
Graphics Design and Realization into the
Multimodal Presentation System WIP
DFKI Technical Memos
TM-91-13
Knut Hinkelmann :
Forward Logic Evaluation: Developing a
Compiler from a Partially Evaluated Meta
In terpreter
16 pages
TM-91-14
Rainer Bieisinger. Rainer Hoch. Andreas Dengel:
ODA-based modeling for document analysis
14 pages
TM-91-1S
Stefan Bussmann: Prototypical Concept
Fonnation An Alternative Approach to Knowledge
Representation
28 pages
TM-92-01
Ujuan Zhang:
Entwurf und Implementierung eines Compilers
zur Transfonnation von
Werkstiickreprasentationen
34 Seiten
TM-92-02
15 pages
Achim Schupeta: Organizing Communication and
RR-92-4S
Elisabeth Andre. Thomas Rist: The Des ign of
Illustrated Documents as a Planning Task
32 pages
Introspection in a Multi-Agent Blocksworld
21 pages
RR-92-46
Elisabeth Andre. Wolfgang Finkler. Winfried
Gra/. Thomas Rist. Anne Schauder. Wolfgang
Wahlster: WIP: The Automatic Synthesis of
Multimodal Presentations
19 pages
TM-92-03
Mona Singh
A Cognitiv Analysis of Event Structure
21 pages
TM-92-04
Jargen Maller. Jorg Maller. Markus Pischel.
Ralf Scheidhauer:
On the Representation of Temporal Knowledge
61 pages
RR-92-47
Frank Bomarius: A Multi-Agent Approach
towards Modeling Urban Traffic Scenarios
24 pages
RR-92-48
Bernhard Nebel. Jana Koehler:
Plan Modifications versus Plan Generation:
A Complexity-Theoretic Perspective
15 pages
RR-92-S1
Hans-Jargen Barckert. Werner Null :
On Abduction and Answer Generation through
Constrained Resolution
20 pages
TM-92-0S
Franz Schmalhofer. Christoph Globig. Jorg
Thoben
The refitting of plans by a human expert
10 pages
TM-92-06
0110 Kahn. Franz Schmalhofer: Hierarchical
skeletal plan refinement: Task- and inference
structures
14 pages
TM-92-08
Anne Kilger: Realization of Tree Adjoining
Grammars with Unification
27pages
RR-92-S4
Harold Boley:
A Direkt Semantic Characterization of RELFUN
30 pages
DFKI Documents
D-92-06
Hans Werner Hoper: Systematik zur
Beschreibung von Werkstiicken in der
Terminologie der Featuresprache
D-92-16
Judith Enge/kamp (Hrsg.): Verzeichnis von Softwarekomponenten fUr natiirlichsprachliche
Systeme
189 Seiten
392 Seiten
D-92-17
D-92-07
Susanne Biundo. Franz Schmalhofer (Eds.):
Proceedings of the DFKl Workshop on Planning
Elisabeth Andre. Robin Cohen. Winfried Graf. Bob
Kass. Cecile Paris. Wolfgang Wahlster (Eds.):
UM92: Third International Workshop on User
Modeling, Proceedings
65 pages
254 pages
D-92-08
Jochen Heinsohn. Bernhard Hol/under (Eds.):
DFKI Workshop on Taxonomic Reasoning
Proceedings
56 pages
D-92-09
Gernod P. Laufkotter: Implementierungsmoglichkeiten der integrativen
Wissensakquisitionsmethode des ARC-TECProjektes
86 Seiten
D-92-l0
Jakob Mauss: Ein heuristisch gesteuerter
Chart-Parser fiir attributierte Graph-Grammatiken
Note: This document is available only for a
nominal charge of 25 DM (or 15 US-$).
D-92-18
Klaus Becker: Verfahren der automatisierten
Diagnose technischer Systeme
109 Seiten
D-92-19
Stefan Dittrich. Rainer Hoch: Automatische,
Deskriptor-basierte Unterstiitzung der Dokumentanalyse zur Fokussierung und Klassifizierung von
Geschiiftsbriefen
107 Seiten
D-92-21
87 Seiten
Anne Schauder: Incremental Syntactic
Generation of Natural Language with Tree
Adjoining Grammars
D-92-11
57 pages
Kerstin Becker: Moglichkeiten der
Wissensmodel-lierung fiir technische DiagnoseExpertensysteme
92 Seiten
D-92-23
Michael Her/ert: Parsen und Generieren der
Prolog-artigen Syntax von RELFUN
51 Seiten
D-92-12
Ouo Kahn. Franz Schmalhofer. Gabriele Schmidt:
Integrated Knowledge Acquisition for Lathe
Production Planning: a Picture Gallery
(Integrierte Wissensakquisition zur
Fertigungsplanung fiir Drehteile: eine
Bildergalerie)
27 pages
D-92-13
Holger Peine : An Investigation of the
Applicability of Terminological Reasoning to
Application-Independent Software-Analysis
55 pages
D-92-14
Johannes Schwagereit: Integration von GraphGrammatiken und Taxonomien zur
Repriisentation von Features in CIM
98 Seiten
D-92-15
DFKI Wissenschaftlich-Technischer
lahresbericht 1991
130 Seiten
D-92-24
Jargen Maller. Donald Steiner (Hrsg .):
Kooperierende Agenten
78 Seiten
D-92-25
Martin Buchheit: Klassische Kommunikationsund Koordinationsmodelle
31 Seiten
D-92-26
Enno Tolzmann:
Realisierung eines Werkzeugauswahlmoduls mit
Hilfe des Constraint-Systems CONT AX
28 Seiten
D-92-27
Martin Harm. Knut Hinkelmann. Thomas Labisch:
Integrating Top-down and Bottom-up Reasoning
inCOLAB
40 pages
D-92-28
Klaus-Peter Gores. Rainer Bleisinger: Ein Modell
zur Repriisentation von Nachrichtentypen
56 Seiten
A Multi-Agent Approach towards Modeling Urban Traffic Scenarios
Frank Bomarlus
RR-92-47
Research Report