In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order
SectionV-CandSectionVIweshowsimulationsanddrawtheconclusionswithfutureperspectives.
II.PRELIMINARYDEVELOPMENTS
Inthissectionwerecalltheconceptsofnetworkofroboticagents,coordinationtasksandcomplexitymeasures,andintroducethenotionofoptimizationundermotionandcommunicationconstraints.
A.Notation
WeletN,N0,andR+denotethenaturalnumbers,thenon-negativeintegernumbers,respectively.Welet andthepositiverealnumbers,i∈{1,...,n}SidenotetheCartesianproductofsetsS1,...,Sn.Forp∈R,welet p and p denotethe oorandceilofp.Forr∈R+andp∈Rd,weletB(p,r)denotetheclosedballcenteredatpwithradiusr,i.e.,B(p,r)={q∈Rd| p q 2≤r}andC(p,r)denotetheclosedhypercubecenteredatpwithsidesoflengthrandparalleltothecoordinateaxes,i.e.,C(p,r)={q∈Rd| p q ∞≤r}.
Forf,g:N→R,wesaythatf∈O(g)(respectively,f∈ (g))ifthereexistn0∈Nandk∈R+suchthat|f(n)|≤k|g(n)|foralln≥n0(respectively,|f(n)|≥k|g(n)|foralln≥n0).Iff∈O(g)andf∈ (g),thenweusethenotationf∈Θ(g).
Next,webrie yreviewsomeusefulproximitygraphs.Givenrcmm∈R+,thediskgraphGdisk(rcmm),respec-tivelycubegraphGcube(rcmm),isthestatedependentgraphonRdde ned[n]bythefollowingstatement:foranypointset{p[1],...,p} Rd,thepair(i,j)isanedgeinG[1]disk(rcmm)·({p[1],...,p[n]}),respectivelyGcube(rcmm)·({p,...,p[n]}),ifandonlyifi=jand p[i] p[j] 2≤rcmm
p[i] p[j]∈B(0d,rcmm),
respectively
p[i] p[j] ∞≤rcmm
p[i] p[j]∈C(0d,rcmm).
AnotherusefulgraphisthecompletegraphGcmpl,i.e.,thegraphwithedgesbetweenanypairofnodes.
Finally,givenagraphG(evennotstatedependent),wedenotewithdistG(i,j)thetopologicaldistancebetweeniandj,i.e.,theminimumnumberofagentstogofromitojinthegraphG.Wede nediamG,thediameterofG,tobethemaximumtopologicaldistance,distG(i,j),forall(i,j).B.Modelinganetworkofroboticagents
Wedescribea(uniform)networkofroboticagentsusingtheformalmodelintroducedin[6]modi edforthediscretetimecase.Thenetworkismodeledasatuple(I,A,Ecmm).I={1,...,n}isthesetofuniqueidenti ers(UIDs);A={A[i]}i∈I={(X,U,X0,f)}i∈IiscalledthesetofphysicalagentsandisasetofcontrolsystemsconsistingofadifferentiablemanifoldX(statespace),acompactsubsetUofRm(inputspace),asubsetX0ofX(setofallowableinitialstates)anda(suf cientlysmooth)mapf:X×U→Xdescribingthedynamicsofithagent;Ecmm:Xn→I×Iiscalledthecommunicationedgemap.
Theroboticnetworkevolvesaccordingtoadiscrete-timecommunicationandmotionmodel.
De nition2.1(Controlandcommunicationlaw):LetSbearoboticnetwork.A(uniform,synchronous,dynamic)controlandcommunicationlawCCforSconsistsofthesets:
(i)L,asetcontainingthenullelement,calledthe
communicationlanguage;elementsofLarecalledmessages;
(ii)W,setofvaluesofsomelogicvariablesw[i],i∈I;(iii)W0 W,subsetsofallowableinitialvalues;andofthemaps:
(i)msg:X×W×I→L,message-generationfunction;(ii)stf:W×Ln→W,calledstate-transitionfunction;(iii)ctl:X×W×Ln→U,calledcontrolfunction. Roughlyspeakingthisde nitionhasthefollowingmean-ing:foralli∈I,totheithphysicalagentcorrespondsalogicprocess,labeledi,thatperformsthefollowingactions.First,ateachcommunicationroundtheithlogicprocesssendstoeachofitsneighborsinthecommunicationgraphamessage(possiblythenullmessage)computedbyapplyingthemessage-generation[i]functiontothecurrentvaluesofx[i]andw.Afteranegligibleperiodoftime,theithlogicprocessresetsthevalueofitslogicvariablesw[i]byapplyingthestate-transitionfunctiontothecurrentvalueofw[i],andtothemessagesreceivedattimet.Betweencommunicationinstants,themotionoftheithagentisdeterminedbyapplyingthecontrolfunctiontothecurrentvalueofx[i],andthecurrentvalueofw[i].Thisideaisformalizedasfollows.De nition2.2(Evolutionofaroboticnetwork):LetSbearoboticnetworkandCCbeacontrolandcommunicationlawforS.Theevolutionof(S,x[i][i]
CC)frominitialconditions0∈X0andw0∈W0,i∈I,isthesetofcurvesx[i]:N→Xandw[i]:N→W,i∈I,satisfying
x[i](t+1)=f x[i](t),ctl(x[i](t),w[i](t+1),y[i](t))
,where,fori∈I,
w[i](t+1)=stf(w[i](t),y[i](t)),
withtheconventionsthatx[i](t0)=x[i]
[i]
i∈I.Here,thefunctiony[i]:N→0andw[i](t0)=wLn(describingthe0,messagesreceivedbyagenti)y[i]
Inthepaper
hascomponents
msg(x[j](t),w[j](t),i),if(i,j)∈Ecmm,j(t)=
null,otherwise.
weconsiderthefollowingnetwork.Eachagentioccupiesalocationp[i]∈Rd,d∈N,andmovesaccordingtothe rstorderdiscrete-timeintegrator
p[i](t+1)=p[i](t)+u[i](t).
(1)
Thecommunicationedgemapcanbeeithertheonearisingaccordingtothediskgraph,Edisk,ortheoneaccordingtothecubegraph,Ecube.Eachcontrolu[i]takesvaluesinaboundedsubsetofRd,thatcanbeeitherB(0,rctr)orC(0,rctr),i.e., u[i] 2≤rctror u[i] ∞≤rctr.Noticethat,ingeneral,thetypeofcommunicationedgemapandthetypeofcontrolboundarenotrelated.Finallythecontrolandcommunicationlawwillbede neddependingonthecoordinationtask.