Coo dina ed con ol s a egies o ne wo ked ehicles:
an applica ion o Au onomous Unde wa e Vehicles
Jo˜ao Bo ges de Sousa and Fe nando Lobo Pe ei a
Depa amen o de Engenha ia Elec o ´ecnica e de Compu ado es
Faculdade de Engenha ia da Uni e sidade do Po o
Rua D . Robe o F ias
4200-465, Po o
Po ugal
{j asso, lp}@ e.up.p
Abs ac
The speci ica ion and design o coo dina ed con ol s a egies o ne wo ked ehicles
and sys ems is discussed. A s a egy o ind he local minimum o an oceanog aphic
scala ield wi h ne wo ked au onomous unde wa e ehicles (AUV) is p esen ed. The
s a egy consis s in coo dina ing he mo ions o he AUVs o implemen a modi ied
e sion o he simplex op imiza ion algo i hm. In he o iginal algo i hm, he scala
ield is gi en by a unc ion. In he modi ied e sion, he scala ield is gi en by he
phenomenon i sel . The AUVs sample he phenomenon o calcula e he di ec ions o
descen , and o minimize he phenomenon along each di ec ion o descen . The s a egy
is discussed in he mo e gene al con ex o coo dina ion and con ol o ne wo ked
ehicles and sys ems.
1 In oduc ion
Today, and pa ly due o ou in ol emen in he design and implemen a ion o ne wo ked
ehicles and sys ems, we ha e a be e unde s anding o he issues a ising in he coo dina ion
and con ol o hese sys ems [9]. In o de o encompass all o hese issues we need o conside
po en ial applica ions om di e se ields, each p esen ing i s own unique challenges o ou
e o s o gene alize and o malize. Recognizing ha we a e s ill aking he i s s eps in his
di ec ion, we ha e been ac i ely in ol ed wi h he po en ial use s o ne wo ked ehicles and
sys ems. This enables us o en ision concep s o he ope a ion o sys ems which could no
ha e been imagined be o e.
In his pape , we p esen some concep s o he ope a ion o au onomous unde wa e e-
hicles, and o mula e he co esponding coo dina ion and con ol p oblems in he se ing o
dynamic op imiza ion. In his se ing, we exp ess complex equi emen s, such as he disjunc-
ion o join -s a e cons ain s and ela i e mo ion coo dina ion, in e ms o in a iance and o
le el se s o alue unc ions. We ocus on mapping se - alued equi emen s, exp essed wi hin
he language o se heo y and logic, on o p oblem o mula ions whe e hese equi emen s
a e exp essed in e ms o se - alued ope a ions.
1
The pape is o ganized as ollows. In sec ion 2, we discuss a p e iew o a mission in ol ing
au onomous unde wa e ehicles o p o ide a conc e e e e en o ou o e iew. In sec ion
3, we discuss he pa e ns o coo dina ion and con ol a ising in his mission and show ha
hey a e qui e gene al, and no speci ic o his applica ion. In sec ion 4, we mo i a e and
illus a e ou speci ica ion and design app oach by e e ence o his mission. In sec ion 5,
we d aw some conclusions and discuss u u e wo k.
2 P e iew o an oceanog aphic mission
Le us s a wi h a p e iew o an oceanog aphic mission concei able in a nea u u e. Imagine
wo eams o Au onomous Unde wa e Vehicles (AUVs) ha mus coo dina e hei mo ions
o ind he local minimum o some oceanog aphic phenomenon.
•The i s eam, deno ed as LPS, p o ides a Local Posi ioning Sys em (LPS) se ice
o o he eam. This sys em can be iewed as an unde wa e e sion o he Global
Posi ioning Se ice (GPS).
•The second eam, deno ed as S, uses he LPS se ice o localiza ion and p o ides a
sea ch se ice.
The Local Posi ioning Sys em wo ks as ollows. Each LPS ehicle has a GPS ecei e and
an acous ic ansponde – he ehicle is equi ed o ope a e a he su ace o ecei e he GPS
signal. The ansponde emi s egula ly, wi h a known equency, an acous ic ping encoding
he ime when i was emi ed, and he name and loca ion o he emi e a ime . The
ime and he posi ion o he emi e a e gi en by he GPS ecei e .
The AUVs om he S eam a e equipped wi h an acous ic sys em. This sys em de ec s
he acous ic pings, and decodes hem o ex ac he posi ion and name o he emi e , and
he ime when he acous ic ping was emi ed. This in o ma ion oge he wi h he ime o
a i al o he ping is used o calcula e he dis ance be ween he AUV and he emi e . To
calcula e i s absolu e posi ion he AUV needs o ecei e pings om a leas h ee sou ces –
ehicles om LPS. In o de o minimize he calcula ion e o we equi e hese h ee sou ces
o be he e ices o a iangle. Due o a enua ion, he LP S se ice is only a ailable wi hin
a neighbo hood P( ) o he LPS eam.
The sea ch se ice wo ks as ollows. The S eam implemen s a modi ied e sion o he
simplex op imiza ion algo i hm o ind he local minimum o he phenomenon. Each ehicle
has a sui e o oceanog aphic senso s – o sample he phenomenon – and a low-bandwid h un-
de wa e acous ic communica ion sys em – o implemen he sea ch s a egy in coo dina ion
wi h he es o he eam and wi h he LP S eam.
In e ms o mo ion coo dina ion he S eam assumes he ole o he leade . The LP S eam
con ols he mo ions o i s ehicles in o de o keep all he elemen s o he S eam inside
P( ). I does his based on he in o ma ion exchanged wi h he S ehicles.
2
He ea e we designa e his mission p e iew as he oceanog aphic mission, o simply he
mission.
3 Coo dina ed con ol o ehicles and sys ems
3.1 Why mo ion coo dina ion?
F om he analysis o he oceanog aphic mission we may in e some o he easons why we
need o coo dina e he mo ions o he e ogeneous ehicles:
Func ional complemen a i y. I is gene ally he case ha space is a p emium in au onomous
ehicles, whe he o sea, ai , o land applica ions. Mo eo e , sensing and sampling s a egies
may equi e he spa ial dis ibu ion no only o senso s, bu also o di e en componen s o
he same sensing sys em. In bo h cases we need o dis ibu e capabili ies – mul iple senso s
o di e en componen s o he same senso – among di e en ehicles.
Spa ial- empo al dis ibu ion o se ices. Some se ices, o example communica ion se ices,
ha e o be dis ibu ed among mul iple ehicles o co e a gi en a ea.
Sensing and ac ing on he wo ld. Sensing in ol es es ablishing spa ial ela ions be ween he
ehicle whe e he senso is moun ed, and he objec o phenomena being sensed. The same
happens wi h ehicles wi h he capabili y o ac upon he wo ld. One such example a ises
wi h Unmanned Comba Ai Vehicles (UCAV), ha a e capable o launching a acks wi h
missiles. Fo he a ack o be e ec i e, we equi e he UCAV o sa is y a p edica e on he
dis ance and azimu h om he a ge be o e a missile is launched.
Algo i hmic mo ion speci ica ions. A a ce ain le el o abs ac ion, ehicles a e poin s in
he 3D space. The mo ion equi emen s o se e al applica ions, o example in he oceano-
g aphic mission, a e exp essed as an algo i hm, ha may, o may no , be implemen able
wi h he mo ions o hose poin s.
3.2 Pa e ns o coo dina ion and con ol
We design eams o p o ide se ices ha canno be p o ided by a single ehicle. This means
ha ehicles wi hin a eam, and eams wi hin in e ac ing eams, ha e o coo dina e hei
ac ions – mo ions and he u iliza ion o hei capabili ies – o p o ide hose se ices. This
is done acco ding o pa e ns o coo dina ion and con ol. Fo example, he ehicles in ou
oceanog aphic mission exhibi pa e ns o coo dina ion and con ol ha a e qui e gene al,
as we will see.
Sa is ac ion o join s a e and capabili y cons ain s. A se ice equi es he sa is ac ion o
p edica es on he capabili ies and on he ela i e mo ions o he ehicles p o iding he se ice.
Team as a speci ic en i y. A eam comes in o exis ence h ough he coo dina ed ac ions o
3
i s ehicles. This means ha , wi h espec o he o he eams, each eam ac s as a single
uni , hus engaging, as a single uni , in in e ac ions wi h hose eams. Fo example, he LPS
ollows he S eam in o de o keep S inside P( ).
Coo dina ion o eams. Se ices may build on o he se ices. In ac , we may need o ec ui
he u iliza ion o se e al eams o deli e a se ice. This equi es he nes ing o se ices,
o cons ain s, and o con olle s. Fo example, he LPS and he S eam join ly p o ide a
sea ch se ice. No e ha he modes o coo dina ion a his le el a e iche han he modes
o coo dina ion a he in a- eam le el. Fi s , eams o m spa ial en i ies whose shape and
e olu ion we may wan o con ol. Second, i may be possible, and desi able, o ans e
asse s among eams.
In e ac ions wi h ex e nali ies. Teams a e designed o in e ac wi h he wo ld, and o in-
e ene in he wo ld h ough sensing and ac ua ion. This means ha we close some o he
con ol loops wi h he ex e nal en i onmen . This ela es o he nex issue.
Algo i hmic based ac i i ies. Teams ha e o in e ac wi h o he eams, o wi h he wo ld. In
he absence o models o he wo ld ha a e based on he p inciples o physics, we ha e o
w i e speci ica ions, and hei implemen a ions, as algo i hms. Fo example, he S eam is
seeking o ind he local minima o an oceanog aphic phenomenon.
Mobili y o links. In o de o coo dina e hei ac i i ies, he ehicles wi hin a eam (e.g.
he S eam), and g oups o eams (e.g. he S and LPS eams), in e ac among hemsel es,
and wi h o he en i ies. To do his, hey es ablish and des oy links among hem. This
means ha hey o m a sys em wi h an e ol ing s uc u e. The s uc u e e ol es when links
change. Hence, es ablishing o des oying a link is a con ol ac ion ha may esul in a
di e en beha io o he s uc u e.
We can ind he same pa e ns o in e ac ions in o he p oblem domains, o example
in applica ions in ol ing Unmanned Ai Vehicles (UAV)s o Unmanned Comba Ai Vehi-
cles (UCAV) (see [8] o an ex ensi e su ey on applica ions o hese ehicles). UAVs and
UCAVs a e in high demand o mili a y, scien i ic and ci ilian applica ions. Mili a y op-
e a ions p esen he mos challenging scena ios. Fo mili a y ope a ions UAVs a e asked
o “di y”,“dull”, and “dange ous” ope a ions. “Di y” e e s o econnoi e ing a eas ha
may be con amina ed, “dull” applies o su eillance, zone in e dic ion o sen y du y, while
“dange ous” is ela ed o ob ious h ea s, such as hose posed by he supp ession o enemy
ai de enses (SEAD). In SEAD missions we ha e spa ial and empo al endez ous whe e
ehicles o m eams. In zone in e dic ion missions we ha e eams o UCAVs ha coo di-
na e hei mo ions o maximize he a e o co e age. In econnaissance and a ge inding
missions we ha e sea ch-based algo i hms wi h in eg a ion o da a om di e en senso s
moun ed on di e en ehicles. Mo eo e , wi h Unmanned Comba Ai Vehicles, we may
wan o emula e he beha io o igh e pilo s, whe e all ypes o engagemen s a e guided
by algo i hmic p ocedu es, o ac ics. Tac ics, also called plays, a e used in obo ic games
4
in ol ing an agonis ic eams o obo s. The collec ion o all ac ics, o plays, is called he
play-book.
4 Illus a ion o he app oach
In his sec ion we mo i a e and illus a e ou speci ica ion and design app oach by e e ence
o he oceanog aphic mission.
4.1 In oduc ion
The po en ially ich beha io o ne wo ked ehicles and sys ems esul s om he way agen s
– ehicles, con olle s, se ice p o ide s, and de ices – a e connec ed, and also om he way
connec ions among hese agen s e ol e wi h ime, i.e. om he con ol a chi ec u e. This is
why we u n ou a en ion o a chi ec u al and speci ica ion issues1.
Ou app oach add esses he issue o o mal speci ica ion, and ea s he design p oblem as
a e inemen o he speci ica ion.
Conside he mission desc ip ion om sec ion 2. Fi s , i is no o mal, i.e., i lacks a
ocabula y o ele an concep s and ules ha de e mine how hey can be used. Second, i
is no comple e, i.e., i does no con ain all componen s, connec ions, e c., in ended o be ue
a all le els o de ail. O , equi alen ly, om i we canno asse which p ope ies will hold
in he implemen a ion, and which p ope ies should no be p esen in he implemen a ion.
Thi d, we canno eason abou he desc ip ion, o p o e ac s abou i .
We add ess hese issues in he ollowing way:
•We ep esen speci ica ions as logical heo ies. We in oduce a ocabula y o he el-
e an componen s and well o medness axioms ha de e mine how hey can be used.
We use se - heo e ic cons uc s ha a e amenable o ma hema ical manipula ion a
he design s age.
•We w i e open speci ica ions o componen s. These speci y he componen i sel , and
no he comple e sys em con aining i .
1The a chi ec u es o la ge sys ems a e o en desc ibed by a hie a chy o ela ed a chi ec u es. A hie a chy
o a chi ec u es is a linea sequence o indi idual a chi ec u es ha may di e wi h espec o he numbe
o componen s and connec ions among hem.
The cu en le el o in o mali y is one o he p oblems wi h a chi ec u al design. Fo example, qui e o en
he e a e no o mal mappings be ween adjacen a chi ec u es in he hie a chy. Hence, i is no possible
o asse ha one a chi ec u e is an implemen a ion o a mo e abs ac one. To be able o answe his
ques ion we need o de ine equi alen beha io s, and we need o s udy unde which condi ions a e beha io s
p ese ed unde hose mappings. This means ha we need mo e han syn ac ic checks; we need o check o
he seman ic p ope ies o an a chi ec u e.
This p oblem has been add essed by he compu e science communi y unde he designa ion o “a chi ec-
u e e inemen ” (see o example, [14]).
5

•We de ine in a ian s, ha we equi e he implemen a ion o sa is y. The in a ian
cap u es he essence o wha makes an implemen a ion co ec . In p ac ice he in a i-
an s de ine he se o beha io s ha sa is y he p edica es associa ed wi h he speci ied
equi emen s.
We o mula e he coo dina ion and con ol p oblems in he se ing o dynamic op imiza-
ion. In his se ing we exp ess complex equi emen s, such as he disjunc ion o join -s a e
cons ain s and ela i e mo ion coo dina ion, in e ms o in a iance, o le el se s o alue
unc ions, and o eachabili y. We ocus on mapping he speci ica ion, exp essed wi hin he
language o se heo y and logic, on o p oblem o mula ions whe e hese speci ica ions a e
exp essed in e ms o se - alued ope a ions. In doing his, we a e able o de i e condi ions
unde which he in a ian s will be ue, and syn hesize con olle s ha ensu e in a iance.
Basically, he design is a e inemen o he speci ica ion.
4.2 Speci ica ion
In his sec ion we in oduce he main concep s and ske ch he speci ica ion o ou mission.
4.2.1 Main concep s
We use simple concep s o speci ica ion: componen s and connec o s. A componen has
an in e nal s uc u e, and a po . A connec o has wo o mo e po s, and speci ies how o
componen s can be linked oge he . We can build componen s om o he componen s, using
connec o s. This allows o hie a chical o ganiza ion. A pa icula a angemen o compo-
nen s and connec o s is e med a con igu a ion. We impose ules on he way componen s
a e connec ed. This de ines a con igu a ion s yle – a ocabula y o design elemen s, well
o medness cons ain s ha de e mine how hey can be used, and a seman ic de ini ion o
componen s associa ed wi h he s yle. The in e ace o a componen de ines a ailable se ices
and condi ions unde which he se ice is p o ided. We connec componen s wi h connec o s
de ining ela ions among he in e aces o hose componen s. Componen s, in e aces, and
connec o s a e ea ed as i s -class objec s – i.e., hey ha e a name and hey a e e inable.
Abs ac a chi ec u al objec s can be decomposed, agg ega ed, o elimina ed on a conc e e
a chi ec u e. The seman ics o componen s is no conside ed pa o an a chi ec u e, bu he
seman ics o connec o s is.
4.2.2 In a and in e - eam speci ica ion
Algo i hm. The S eam implemen s a modi ied e sion o he simplex algo i hm ha is
desc ibed nex . We could ha e used ano he algo i hm. This one su ices o illus a e ou
app oach in spi e o i s simplici y.
Conside , o he sake o simplici y, a scala ield (x) : <2→ < e ol ing in he ho izon al
plane wi h a unique local minimum in he egion o in e es . We a e in e es ed in inding
6
his minimum.
A he beginning o each i e a ion i, we ha e h ee poin s Ai, Bi, Ci, and h ee alues o he
scala ield (Ai), (Bi), (Ci), whe e we ha e labelled he poin s so ha (Ai)≤ (Bi)≤
(Ci). The sequence o compu a ions is desc ibed nex .
Algo i hm 1 (Modi ied simplex). Se i:= 1. Conside h ee poin s A1, B1, C1 o ming
a iangle. Repea un il inding minimum.
1. Take he segmen joining Aiand Bi. De ine he midpoin o his segmen as zi. De ine
he cone K(zi)wi h apex a zio all he uni ec o s om Ci o zi+δ×B, whe e δis
a pa ame e and B he uni ball.
2. De ine he se o easible di ec ions a zias K(zi).
3. Selec one ec o om K(zi).
4. I , a zi, and o any di ec ion wsuch ha hw, i ≥ 0, he di ec ional de i a i e o
along wis non-nega i e, i.e., 0(zi;w)≥0, hen s op. In his si ua ion, he poin
o minimum is loca ed wi hin he iangle wi h e ices Ai,Bi, and Ci. I no hen,
s a ing a zi, ind he minimum o in he di ec ion o . Deno e he poin whe e he
minimum is a ained as Ai+1. Then (Ai+1)≤ (Ai)≤ (Bi)≤ (Ci).
5. Rename Aiand Bias Bi+1 and Ci+1.
6. Se i:= i+ 1.
This algo i hm is scalable wi h espec o he numbe o ehicles used o implemen i .
Wi h one ehicle, he ideal implemen a ion would equi e his ehicle o jump om poin
Ai+1 o poin zi+1 a he beginning a each new i e a ion. Wi h wo ehicles, he ideal
implemen a ion would equi e one o hem o be a posi ion zi+1 when he o he eaches he
poin Ai+1.
A ailable asse s. Conside he ollowing asse s.
1. A se SV, o nSV iden ical su ace ehicles wi h a GPS ecei e , a ansponde , a adio,
and an acous ic modem. The anges o he adio, ansponde s, and acous ic modems
a e espec i ely , and a.
2. A se AUVu, o nuiden ical AUVs wi h a Conduc i i y Tempe a u e Dep h (CTD)
senso , an acous ic modem, and a na iga ion acous ic sys em. The ange o he acous ic
modem is a.
3. A se AUVs, o nsiden ical AUVs moun ing he same de ices as he su ace ehicles,
plus he senso pack moun ed on all he ehicles om AUVu. These mul i- ole ehicles
may be assigned o he LPS, o o he S eams.
7
We use he su ace ehicles o implemen he LP S eam, and he AUVs o implemen
he LPS, and S eams. The LPS eam is composed o wo se s o ehicles, LPSSV and
LPSAUV , whe e LPSSV =SV, and LPSAUV ⊆ AUVs. The S eam is also composed o wo
se s o ehicles, Suand S , whe e Su=AUVu, and S ⊆ AUVs.
We label each ehicle in S(LPS) wi h a numbe i(j), whe e i(j) anges om 1 o nS( )
(nLP S( ))), and nS( ),(nLP S ( )) a ies wi h ime. We deno e he (x,y,z) posi ion o he
i− h(j− h) ehicle om S(LPS) by XSi( ),(XLP Si( )).
Dis ance unc ion. In wha ollows we exp ess he Euclidean dis ance be ween wo poin s
X, Y in <3as d(X, Y ).
Fi s , we speci y he beha io o each eam, and hen he equi ed in e - eam beha io .
LPS eam. The LPS eam p o ides a posi ioning se ice o o he ehicles. A ime , he
se ice is a ailable a all loca ions Xsuch ha he e a e a leas h ee ehicles om LP S
wi hin dis ance – he ange o he ansponde – om X. The se o all such poin s is
deno ed P( ).
P( ) = {X∈ <3:∃i, j, k (k6=i)∧(i6=j)∧(j6=k)∧(d(XLP Sj, X)≤ )∧
(d(XLP Si, X)≤ )∧(d(XLP Sk, X)≤ )}(4.1)
The ehicles in LPS mus sa is y he ollowing mo ion cons ain s2.
Se ice cons ain s. A leas h ee ehicles om LPS a e equi ed o o m a iangle. We
exp ess a elaxed e sion o his equi emen using he dis ance unc ion das ollows:
∃i, j, k ∈LPS : (j6=i)∧(i6=k)∧(k6=j)∧(d1≤d(XLP Si, XLP Sj)≤d2)∧
(d1≤d(XLP Si, XLP Sk)≤d2∧(d1≤d(XLP Sk, XLP Sj)≤d2) (4.2)
S uc u al cons ain s. The LPS ehicles ha e o coo dina e hei mo ions o sa is y he
se ice cons ain s, and o ollow he S eam. This is why we equi e he LPS ehicles o o m
a communica ion ne wo k whe e e e y wo dis inc ehicles should be able o communica e
be ween hem. We exp ess he equi emen as g aph connec edness. To exp ess g aph
2The e a e wo dis inc ypes o cons ain s. The ones equi ed o he eam o coo dina e i s ope a ions
and o main ain i s in eg i y, le us call hem he s uc u al cons ain s, and he ones equi ed o he eam
o p o ide se ices, le us call hem he se ice cons ain s. The s uc u al cons ain s ha e p ecedence o e
he se ice cons ain s. The iola ion o he o me implies he collapse o he eam, while he iola ion o
he la e deg ades he way he se ice is deli e ed. F om he abo e we conclude ha we a e in he p esence
o wo le els o dynamic beha io . The i s one ensu es ha he s uc u al cons ain s a e an in a ian se
o he ope a ion o he eam, he in e nal dynamics. The second one ensu es se ice deli e y, he ex e nal
dynamics. The wo le els o dynamic beha io a e ob iously coupled. We wan o con ol his coupling so
ha he eam is able o espond o se ice eques s as as as possible. This p ope y is called lexibili y.
The speci ica ion o bo h ypes o cons ain s should be scalable o accommoda e he addi ion, o dele ion,
o ehicles o and om he eam.
8
connec edness o mally we need some e minology and no ions om g aph heo y3. De ine
he g aph T as ollows. Each ehicle in LPS is ep esen ed by a e ex. The e is an edge
be ween wo e ices whene e he dis ance be ween he co esponding ehicles is less han
he adio communica ion ange . The communica ion cons ain s a e exp essed as ollows:
The g aph T is connec ed (4.3)
S eam. The ehicles om he S eam implemen a modi ied e sion o he simplex algo-
i hm. The implemen a ion o his algo i hm equi es pe manen communica ion among he
ehicles. He e, again, we need g aph connec edness in a g aph K de ined as ollows. To each
e ex in V he e co esponds a ehicle in S. The e is an edge be ween wo e ices whene e
he dis ance be ween he co esponding ehicles is less han a. The cons ain is exp essed
as:
The g aph K is connec ed (4.4)
LPS-S coo dina ion. The e a e wo coo dina ion equi emen s:
1. The ehicles om he S eam should emain inside he se P( ):
∀i∈S:XSi( )∈P( ) (4.5)
2. The ehicles in bo h eams should be able o communica e among hemsel es. I ais
he maximum ange o communica ion we exp ess his cons ain as ollows:
∀ , ∀i∈S, ∀j∈LPS :min d(XLP Sj( )), XSi( )) ≤ a(4.6)
Task. Con ol he mo ions and se ices o he wo eams o ind he minimum o he em-
pe a u e in a gi en zone o he ocean in minimal ime, and using he simplex algo i hm.
4.2.3 Rema ks
Now, a he in o mally, le us conside his speci ica ion in he ligh o he concep s in o-
duced be o e, i.e., componen s and connec o s.
Conside he S eam. We speci y his eam as a componen . The in e ace o he eam
includes, as ou pu s, he sea ch se ice, he se CS( ) – he con ex closu e o he loca ions
o he membe s o he eam) – and he se DS( ) – he se o loca ions whe e o he ehicles
can communica e wi h his eam – and, as inpu s, a localiza ion se ice o he whole eam.
The LPS eam is ea ed analogously. The in e ace includes, as ou pu s, he posi ioning
3A g aph G is a ini e nonemp y se V oge he wi h an i e lexi e symme ic ela ion R on V. V is he
e ex se . We deno e by E he se o symme ic pai s in R. Each elemen in E is called and edge, and he
se E is called he edge se o G. A u- walk in G is an al e na ing sequence o e ices and edges o G,
beginning wi h u and ending wi h , such ha e e y edge joins he e ices immedia ely p eceding i and
ollowing i . Two e ices u and in a g aph G a e connec ed i u= , o i u6= and a u- pa h exis s in
G. A g aph is connec ed i e e y wo e ices o G a e connec ed.
9