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
C.Coordinationtasksandtimecomplexity
Wearereadytode nethenotionoftaskandoftaskachievementbyaroboticnetwork.
De nition2.3(Coordinationtask):LetSbearoboticnetwork.nA(static)coordinationtaskforSisamapT:X→{true,false}.Additionally,letCCacontrolandcommunicationlawforS.Theforallinitialconditionsx[i]lawCCachievesandw[i]
thetaskTif,
0∈X00∈W0,i∈I,thecorrespondingnetworkevolutiont→(x(t),w(t))hasthepropertythatthereexistsT∈NsuchthatT(x(t))=trueforallt≥T. Weare nallyreadytode nethenotionoftimecom-plexityastheminimumnumberofcommunicationroundsneededbytheagentstoachievethetaskTwithCC.
De nition2.4(Timecomplexity):LetSbearoboticnet-workandletTbeacoordinationtaskforS.LetCCbeacontrolandcommunicationlawforScompatiblewithTThetimecomplexitytoachieveTwithCCfromx0∈X0n
.
isTC(T,CC,x0)=inf{T∈N|T(x(t))=true, t≥T}wheret→(x(t),w(t))istheevolutionof(S,CC)fromtheinitialcondition(x0,w0).
ThetimecomplexitytoachieveTwithCC,TC(T,CC),isthemaximumTC(T,CC,x0)overallinitialconditionsx0.D.OptimalcontrolandcommunicationinroboticnetworksHavingde nedacoordinationtaskforaroboticnetwork,wecanaskwhethersuchtaskcanbeaccomplishedminimiz-ingsomecostfunctional.Inwhatfollowswewillintroducethenotionofoptimalcontrolandcommunicationproblemandofoptimalcontrolandcommunicationlawassolutionoftheproblem.
De nition2.5(Optimalcontrolandcommunication):GivenataskTandacostfunctionalJ(u(·),x(T),T),anoptimalcontrolandcommunicationproblemisthefollowing:minimizeu(·),x(0),x(T),TJ(u(·),x(T),T)
J(u(·),x(T),T)= T
τ=0(l(x(τ),u(τ))+g(x(T)),subj.to
(i)(x(·),u(·))isaninput-statetrajectoryofA,
A={A[i]}i∈I;
(ii)iandjcancommunicateifandonlyif
(i,j)∈Ecmm(x[1](t),...,x[n](t));(iii)T(x(t))=trueforallt≥T,T∈N.
wherel:Xn×Un→Risasuf cientlysmoothand
nonnegative-valuednfunction,calledstagecost,andg:X→Rhasthesamepropertiesplusg(x)=0forallx∈XnsuchthatT(x)=true(foranadmissibleCC). WesaythatacontrolandcommunicationlawCCisoptimalwithrespecttothecoordinationtaskTandthecostfunctionalJ,ifitsolvestheaboveoptimalcontrolandcommunicationproblem.
WecallCCacentralizedoptimalcontrolandcommunica-tionlawifitsolvestheoptimizationproblemforanetworkofroboticagentsthatcommunicateaccordingtothecompletegraph,i.e.,thecommunicationedgemapisEcmpl.
Remark2.6:Thecentralizedsolutionofanoptimalcon-trolandcommunicationproblemistheclassicalsolutionoftheoptimalcontrolproblemforthewholenetworksystemwithoutcommunicationconstraints.
III.CENTRALIZEDMINIMUM
TIMERENDEZVOUS
Inthissectionwestudytherendezvousproblemforaroboticnetworkof rstorderagentswithcommunicationedgemapEdiskorEcubeandlookforacontrolandcommu-nicationlawthatsolvestheprobleminminimumtime.Moreformally,letS=(I,A,Ecmm)beauniformroboticnetwork.The(exact)rendezvoustaskTrndzvs:Xn→{true,false}forSis thestatictaskde nedby
true,
ifx[i]=x[j],Trndzvs(x)=forx=(x[1],...,x[n (i,j)∈Ecmm(x),
false,otherwise.
]).
Thus,giventheuniformnetworkS=(I,A,Ecmm),theminimumtimerendezvousproblemfor rstorderagentswithlimited-rangecommunicationandboundedcontrolinputisthefollowing:
minimizeu(·),p(T)
Tτ=01,subj.to
(i)(p(·),u(·))isaninput-statetrajectoryofA,
A={A[i]}i∈I={(Rd,U,Rd,f)}i∈I,p(0)=p0;(ii)iandjcancommunicateif[nand]onlyif
(i,j)∈Ecmm(p[1](t),...,p(t));
(iii)Trndzvs(p[1],...,p[n])=trueforallt≥T,T∈N.Herei]UiseitherB(0,rctr)orC(0,rctr),f(p[i](t),u[i](t))=p[(t)+u[i](t)andthecommunicationedgemapEcmmiseitherEdiskorEcube.
WerefertotheminimumtimerendezvousproblemwithcommunicationedgemapEcmmandinputsetUasMTR(Ecmm,U).
Next,weprovidesomepreliminaryresultsforthecentralizedsettingoftheaboveproblem,]thatis,forMTR(Ecmpl,U).LetMEB(p[1]···p[n)andMEO(p[1]···p[n])theminimalenclosingballandorthotopeofpoints(p[1]·]··p[n]),andletMBC(p[1]···p[n][n])andMOC(p[1]···p[n[n])thecentersofMEB(p[1]···p)andMEO(p[1]···p)respectively.Wepresentthefollowingtheoremomittingtheproofbasedongeometricargumentsbecauseofspaceconstraints.
Theorem3.1:Forallrctr∈R+,p[i]
),U0∈Rd,i∈{1,...,n}thesolutionofMTR(Ecmpl,U=B(0,rctr)orU=C(0,rctr),isnotunique(theproblemisnotnormal).Ifu[i]∈B(0,rctr),i∈{1,...,n},then
(i)p(T)=prndzvs,disk=MBC(p[1](0),...,p[n](0)),
u[i](t)=min{rctr, prndzvs p[i](t) 2}
·vers(prndzvs p[i](t)),
i∈{1,...,n},
isasolutionofMTR(Ecmpl,B(0,rctr));
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