• Non ci sono risultati.

Adaptability checking in complex systems

N/A
N/A
Protected

Academic year: 2021

Condividi "Adaptability checking in complex systems"

Copied!
24
0
0

Testo completo

(1)

Contents lists available atScienceDirect

Science

of

Computer

Programming

www.elsevier.com/locate/scico

Adaptability

checking

in

complex

systems

Emanuela Merelli

a,

, Nicola Paoletti

b

, Luca Tesei

a

aSchoolofScienceandTechnology,ComputerScienceDivision,UniversityofCamerino,Via delBastione 1,62032,Camerino,Italy bDepartmentofComputerScience,UniversityofOxford,ParksRoad,OX1 3QD,Oxford,UK

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received17February2013

Receivedinrevisedform16December2014 Accepted26March2015

Availableonline1April2015 Keywords: Adaptivesystems Statemachine Adaptabilityrelations Adaptabilitychecking S[B]model

A hierarchical approach for modelling the adaptability features of complex systems is introduced. It is based on a structural level S, describing the adaptation dynamics of the system, and a behavioural level B accounting for thedescription ofthe admissible dynamicsofthesystem.Moreover,aunifiedsystem,called S[B],isdefinedbycouplingS and B.Theadaptation semanticsissuchthat the S level imposesstructural constraints on the B level, which has to adapt whenever it no longer can satisfy them. In this context,weintroduceweakand strong adaptability,i.e.theability ofasystemtoadapt forsomeevolutionpathsorforallpossibleevolutions,respectively.Weprovidearelational characterisationforthesetwonotionsandweshowthatadaptabilitychecking,i.e.deciding if a system is weakly orstrongly adaptable, can be reduced to aCTL model checking problem. Weapply themodel and thetheoretical resultstothe casestudyofamotion controllerofautonomoustransportvehicles.

©2015TheAuthors.PublishedbyElsevierB.V.Thisisanopenaccessarticleunderthe CCBY-NC-NDlicense(http://creativecommons.org/licenses/by-nc-nd/4.0/).

1. Introduction

Self-adaptivesystemsareparticularsystemsabletomodifytheirownbehaviouraccordingtotheircurrentconfiguration andtheperceptionoftheenvironment inwhichtheyoperate.Theydevelopnewstrategiesinordertofulfilan objective, properlyrespondtochangesoftheenvironmentalconditionsor,moregenerally,maintaindesiredconditions.

Fromabroadviewpoint,self-adaptivenessisanintrinsicpropertyofcomplexnaturalsystems.Self-adaptationisaprocess drivingboth theevolutionandthe developmentoflivingorganismsthatadapttheir featuresandchangetheirphenotype inorder tosurvive to thecurrenthabitat, toachieve higher levelsof fitnessandto appropriately react to external stim-uli.

Nowadays, software systems are increasingly resembling complex systems; thismotivates the development of meth-ods forenabling softwareself-adaptiveness.Similarly to naturalsystems,“Self-adaptive software evaluates its own behaviour and changes behaviour when the evaluation indicates that it is not accomplishing what the software is intended to do, or when bet-ter functionality or performance is possible”[35].Self-adaptivesoftwarefindsapplicationinfieldslikeautonomiccomputing, service-oriented architectures,pervasive service ecosystems,mobile networks, multi-agent systems, and ultra-large-scale softwaresystems[25],characterisedby distributed,autonomous,interacting,heterogeneous,conflictingandevolvable sub-systems.

Inthiswork, wedevelop aformal hierarchicalmodelforself-adaptivesystems,wheretwo fundamental levelsare de-fined:the

behavioural level B,

whichdescribestheadmissibledynamicsofthesystem;andthe

structural level S,

accounting

*

Correspondingauthor.

E-mailaddresses:emanuela.merelli@unicam.it(E. Merelli),nicola.paoletti@cs.ox.ac.uk(N. Paoletti),luca.tesei@unicam.it(L. Tesei). http://dx.doi.org/10.1016/j.scico.2015.03.004

0167-6423/©2015TheAuthors.PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBY-NC-NDlicense (http://creativecommons.org/licenses/by-nc-nd/4.0/).

(2)

fortheinvariantfeaturesofthesystemthatregulatethebehaviourofthesystem.Moreprecisely,bothlevelsaremodelled asstatemachines, buteachstate ofthe S level isassociatedwitha setof

constraints,

i.e.logicalformulasoverobservable variablesofthe B level.

An

S state

inthestructurallevelrepresentsarelativelypersistentsituation,asteadyregionforthe

B level,

identifiedby thesetof B states satisfyingtheconstraints.Therefore S is a

higher order structure whose

statescanbeinterpretedassets of B states, andwhosetransitionscanbeviewedasmappingsamongsetsof B states. Thecoupledmodelwillbereferred toas

S

[

B

]

,inordertohighlightthetwobasiclevelsthatcomposethesystem.

The S

[

B

]

modelis broadlyinspired bya previous work ofsome ofthe authors,a spatial bio-inspired processalgebra called

Shape

Calculus[3,4],whereprocessesarecharacterisedbyareactivebehaviour B and byashape

S that

imposesaset ofgeometricalconstraintsontheirinteractionsandoccupancyinthethree-dimensionalEuclideanspace.Here,instead,the computationalapproachisshiftedinamoregeneralcontext,where S and B are coupledbyahierarchicalrelationdefined onthestructuralconstraintsofthe S level andthestatespaceofthe B level.

The adaptationsemanticscan bebriefly described asfollows.Consider an S

[

B

]

system, let

q be

thecurrentstateof B

and assumethat it satisfiesthe constraintsofthe current S state. The adaptation istriggered whenever

q cannot

evolve because thereis nonext B state that satisfiesthe current S constraints. Duringadaptation, the S

[

B

]

systemattempts to evolve towardsa newB state thatsatisfiesa new S state, chosen amongthesuccessorsofthecurrentone. Inthisphase

B is nomoreconstrainedby S. Adaptationterminatessuccessfullywhen B ends upin astate thatfulfils thenewglobal situationrepresentedbyoneoftheadmissible S states.

Afirstgeneralintroductionofthe

S

[

B

]

modelwasgivenin[38]and[39]bytheauthors.Inthiswork,weprovideseveral noveltiesandimprovements,mostofthem devotedtothe

adaptability checking problem,

i.e.theautomatic checkingofthe adaptationcapabilitiesofagiven

S

[

B

]

system.Inparticular,wedefinethenotionof

weak adaptability,

possessedbyan

S

[

B

]

systemthatisabletoadaptalongsomeofallitspossibleevolutionpaths.

Strong adaptability requires

thatthe

S

[

B

]

system isabletoadaptalongallitspossibleevolutionpaths.Weformulatethenotionsofweakandstrongadaptabilityasrelations betweenthestatesof

B and S and

alsoinlogicalform,asComputationTreeLogic(CTL)formulasoverthegivensemantics ofan

S

[

B

]

system.Then,weformallyprovetheequivalencebetweentherelationalandthelogicalformulationofstrongand weakadaptability(Theorems 1 and 2),showingthattheadaptabilitycheckingproblemcanbereducedtoaclassicalmodel checkingproblem. Wealsodiscussthecomputationalcomplexity ofourapproach.Theeffectivenessofthe S

[

B

]

approach for self-adaptivesystems is demonstratedusing acase studyinthe context ofadaptive softwaresystems, a modelfora motion controllerofautonomoustransport vehicles inasmart airport.The samecasestudyisusedforexemplifying the notionsofweakandstrongadaptabilityandtheadaptabilitycheckingproblem.

The paper is organised as follows. Section 2 introduces the formalism and the syntax of the S

[

B

]

model. Section 3

illustrates theapplicationofthemodeltotheexampleofadaptivemotioncontroller.InSection4we givetheoperational semantics of an S

[

B

]

systemby means ofa flattened transitionsystem. In Section 5 we formalisetherelations of weak andstrongadaptation,whichweequivalentlycharacteriseasCTLformulasinSection6.Relatedworksincludingadaptation featuresof S

[

B

]

,andconclusionsaregiveninSection7.Finally,proofsarepresentedinAppendix A.

2. Aformalhierarchicalmodelforadaptivesystems

Inthe S

[

B

]

approach,amodelencapsulatesboththebehavioural(B)andthestructural(S)levelofanadaptivesystem. The behavioural level is classically described as a finite state machine of the form B

= (

Q

,

q0

,

→B

)

where Q is a set

of B states, q0 initial B state and

→B

transition relation.The structurallevel ismodelled asa finite state machine S

=

(

R

,

r0

,

O,

→S

,

L

)

where R is a set of S states, r0 is theinitial S state,

O

isan observation function,

→S

isa transition

relationand

L is

astatelabellingfunction.Thefunction

L labels

each

S state

withaformularepresentingasetofconstraints over an

observation of

the B states. Thereforean S state r can bedirectly mapped tothe setof B states satisfying L

(

r

)

. Through thismapping, S can beviewedasa

second-order structure

S

= (

R

2Q

,

r0

,

O,

→S

R

×

R

)

whereeach S state r

isidentifiedwithitscorrespondingsetof

B states.

An S

[

B

]

systemistheresultofcouplingthetwolevels

S and B through

the observation function

O

andan evaluationfunction

[[·]]

, that maps each S state to the set of B states meeting the constraints.

The S

[

B

]

adaptation is achievedby switchingfroman S state to another S state where a differentsetof constraints holds. During adaptationthe B machine is no moreregulated by the structurallevel,except foran adaptation invariant, called

adaptation invariant,

thatmustbefulfilledbythesystemwhileadapting.Thesystemadaptsbyfollowinganytrajectory thatispresentatthe B level thatdoesnotviolatetheinvariantcondition,whichcanbeusedasasafetyconditionifsome activitiesofthe

B level

mustbeavoidedduringadaptation.

Inordertorealiseournotionof S

[

B

]

adaptiveness,theremustbesomeinformationflowingbothfromB to S and vice versa. Inparticular,theinformationfrom B to S is modelled hereasa setofvariables A

= {

a1

,

. . . ,

an}called

observables

of the S on the B level. Thevaluesof thesevariablesmustalways be

derivable from

theinformationcontainedin the B

states.Thismakesourapproachblack-box-oriented,thatistosay,

S has

notthefullknowledgeof

B,

butonlysomederived information.

(3)

Fig. 1. AdaptationloopinanS[B]system.Ateachstep,S observesB anddecideifthereisaneedtochangestate.Theloopcloseswiththeselectionof eligiblenextstatesB ofB,i.e.thosethatsatisfythecurrentconstraintsorthosethatsatisfythecurrentadaptationinvariant.

Incontrol-theoreticterms,asillustratedinFig. 1,theadaptationmodelofan

S

[

B

]

systemcanbeviewedasaclosed-loop systemwhere B is theplantand S is the controller.Let

q and

r be thecurrentstatesof B and S. B outputs thevector1

B

=

Post

(

q

)

ofthe statesreachablefrom

q with

a single transition,i.e.an element

q

i of B issuch that

q

→B

qi andeach

state is unique:



i=jqi

=

qj.Since S can only observesome features of B states, the observer

O

will provide S with a

vectorofobservationsmadeoverthevaluesofthevariablescharacterising eachstateinB:o

=



i

O(

qi

)

.

S will checktheobservablesprovidedbyo withrespecttoitscurrentstate

r.

Ifitsconstraintsaresatisfied,

S will

remain inthesamestateandS

[

B

]

willproceedin

steady mode.

Otherwise,

S will

performatransitiontoanew

r state

forcingthe

S

[

B

]

systemtoenteran

adaptation mode.

Hereweassumethattheupdated

r is

computedwithafunction

Check that

takes thecurrentS state andobservations.ThefeedbackloopcloseswiththeselectionoftheeligiblenextstatesB outputtedto

B, i.e.thosestatesthatsatisfythecurrentconstraintsof

r or

thosethat satisfythecurrentadaptationinvariant. ThesetB

isobtainedbyapplyingtheevaluationfunction

[[·]]

toeithertheconstraintsof

r or

theinvariant. Intheadaptationmode the outputis calculatedusing thewhole B machine without constraintsexceptthe adaptationinvariant, to make B free

toexplore thestatespace. Inturn, B updates its currentstate

q by

selectingone oftheeligiblestatesprovidedinB.The conceptsofobservationfunction

O

andevaluationfunction

[[·]]

areformalised inDefinition 1andDefinition 2.

2.1. Language for constraints

Theconstraints characterisingthe statesofan S level are expressedusingformulas ofamany-sorted firstorderlogic. Moreprecisely,thedefinitionofan

S level

includesthedefinitionofamany-sortedsignature



containingsomefunction symbols,somepredicatesymbolsandsomesortsD1

,

. . . ,

D

k.



-termsand



-formulasareconstructedinthestandardway [24].Inaddition,a particularset ofsortedvariables, whichwe callobservables, mustbe fixed. Sucha setis oftheform

A

= {

a1:

D

j1

,

. . . ,

an:Djn

}

,where ji

∈ {

1

,

. . . ,

k

}

forall

i

=

1

,

. . . ,

n. Then,constraintscanbeexpressedas



-formulas

ψ

such thatthevariablesthatoccurfreein

ψ

,denotedbyfree

(ψ)

,area(possiblyempty)subsetofA. Thissetwillbedenotedby

(,

A

)

= {ψ | ψ

is a



-formula

free

(ψ)

A

}

.

We also impose that a particular structure M is fixed for the evaluation of



-formulas. M consists ofk non-empty

domains M

(

D1

),

. . . ,

M

(

Dk

)

, ascarriersets forsorts,together withinterpretations forall function andpredicatesymbols

of



.Toobtainthefullsemanticevaluationofformulasin

(,

A

)

wewilltakethevaluesforthefreevariablesin

A from

anobservationfunction.

Definition1

(Observation function).

Let

Q

betheuniversesetofallstatesofmachinespossiblyrepresenting B levels. Let



beamany-sortedsignature,let A

= {

a1:

D

j1

,

. . . ,

an:Djn

}

beasetofobservablesandlet

M be

astructurefortheevaluation of



-formulas.An

observation function

O

,A

M on



,A and M is apartialfunction

O

,A

M :

Q



→ (

A

D

)

where(i)

D =

n

i=1M

(

Dji

)

and(ii)foranystate

q

Q

,if

O

,MA

(

q

)

=⊥

then

O

,A

M

(

q

)(

ai:

D

ji

)

M

(

Dji

)

,forall

i

=

1

,

. . . ,

n.

Foralighternotation,wewilluse

O

insteadof

O

,MAwhen

,

A and M are

clearfromthecontext.

Notethattheuseoftheuniverseofstatesasdomainmakesthedefinitionoftheobservationfunctionindependentfrom aparticularstate machinerepresentingabehaviourallevel B. Notealsothatwedonotrequiretheobservationfunctionto beinjective.Thismeansthatsomedifferentstatescangivethesamevaluestotheobservables.Inthiscase,thedifference amongthestatesisnotvisibleto S through theobservation,butitisinternalto B.

Tocompletethemachineryforcheckingwhetherasetofconstraintsissatisfiedornot,wedefinethesatisfactionrelation inthenaturalway.

(4)

Definition2

(Satisfaction

relation). Let

O

,MAbeanobservationfunction.Astate

q

Q

satisfies a formula

ψ

∈ (,

A

)

, writ-ten

q

| ψ

,iff

O

,MA

(

q

)

=⊥

and

ψ

istrue,accordingtothestandardsemanticsofmany-sortedfirstorderlogic,withrespect tothestructure

M and

bysubstitutingin

ψ

everyoccurrenceofthefreesortedvariable

a

i:Dji with

O

,MA

(

q

)(

ai:

D

ji

)

.

Wealsodefineanevaluationfunction

[[·]]

: (,

A

)

2Qmappingaformula

ψ

∈ (,

A

)

tothesetofstates

[[ψ]]

=

{

q

Q

|

q

| ψ}

,i.e.thosesatisfying

ψ

.

A setofconstraintsisformally expressedbya formula

ψ

∈ (,

A

)

thatis theconjunctionofalltheformulas repre-sentingeachconstraintintheset.Thesetofconstraintsissatisfiedifandonlyifthecorrespondingformulaistrueinthe fixedstructure M and observation

O

,MA.

Example1.Letusconsiderasetofobservablesandassociatedsorts:

A

= {

velocity

: R,

congestion

: B}

Consider alsoasignature



= {R,

B,

==,

>,

<,

0

,

5

}

where

R

and

B

are thesortsindicatingthedomainsofrealnumbers andboolean,respectively;

==

isthe equalitypredicateinterpreted asthe identityrelationineach domain;

>

and

<

are theusualgreater-thanandless-thanpredicatesover

R

;andtheconstants0 and5 aretherealnumbers0 and5.Apossible formula

ψ

inthelanguage

(,

A

)

is

congestion

velocity

<

5

∧ ¬

congestion

velocity

>

0

whosesatisfactiondependsontheparticularvaluesofthevariables,whichwillbedifferentindifferentstates.

InthecontextofAutonomousTransportVehicles(seeSection 3),thisformulacanbethoughttorepresentasetoftwo constraints,oneimposingthat“incaseofcongestion, thevelocityofthevehiclemustbelowerthan5”andtheotherthat “innormaltrafficconditions,thevelocitymustbegreaterthan 0”.

2.2. Coupling S and B

Letusnowformally definethebehaviourallevel B and thestructurallevel S separately. Afterwards,the S

[

B

]

modelis definedasthecombinationofthetwo.

Definition3

(Behavioural level).

Thebehaviourallevelofasystemisatuple

B

= (

Q

,

q0

,

→B

)

,where

Q

Q

isa

finite set

ofstatesand

q

0

Q is theinitialstate;and

• →B⊆

Q

×

Q is thetransitionrelation.

Definition4

(Structural level).

ThestructurallevelofasystemisatupleS

= (

R

,

r0

,

O

,MA

,

→S

,

L

)

,where

R is afinitesetofstatesand

r

0

R is theinitialstate;

O

,A

M isanobservationfunctiononasignature



,asetofobservablesA and astructure

M;

• →S

R

× (,

A

)

×

R is afinitetransitionrelation,labelledwithaformulacalled

invariant;

and

L

:

R

→ (,

A

)

isafunctionlabellingeachstatewithaformularepresenting

a set of constraints.

Letusnowgiveanintuitionoftheadaptationsemantics.Letthecurrent

S state

be

r

iandsuppose

r

i

ψ

−→S

rjforsome rj.

Assumethatthebehaviourisinasteadystate(i.e.notadapting)

q

iandtherefore

q

i

|

L

(

ri

)

.Ifthe

B state

canmove,butall B transitions qi

→B

qjaresuchthat

q

j

|

L

(

ri

)

,thenthesystemcanstartadaptingtothetarget

S state r

j.Inthisphase,the B level isnomoreconstrained, butduring adaptationtheinvariant

ψ

mustbemet.Adaptationendswhenthebehaviour reachesastate

q

ksuchthat

q

k

|

L

(

rj

)

.

Wewanttoremarkthatthemodelsupportsthenon-deterministicchoicebetweenadaptations,i.e.thesystemcanadapt to everytarget state

r

j reachablewithatransition

r

i

ψ

−→S

rj fromthecurrent

r

i state.The non-determinismcanbe both

external—thatisdifferenttargetstatescanbereachedbysatisfyingdifferentinvariants—andinternal—thatisdifferenttarget statescanbereachedsatisfyingthesameinvariantcondition.

Definition5

(S

[

B

]

system). An

S

[

B

]

system is thecombinationofabehaviourallevel B

= (

Q

,

q0

,

→B

)

andastructurallevel

S

= (

R

,

r0

,

O

,MA

,

→S

,

L

)

suchthatforall

q

Q ,

O

,A

M

(

q

)

=⊥

.Moreover,inanyS

[

B

]

systemtheinitial

B state

mustsatisfy

(5)

Fig. 2. Aschemaofstatesandtransitionsstartingfromagenericstate(r,v,c,0,0).Weletr =r.Moreover,thetransitionstowardsthestates(r,v+ 1,c,0,0)or(r,v+1,¬c,0,0)arenotpresentwheneverv=2,whilethetransitionstowardsthestates (r,v−1,c,0,0)or(r,v+1,¬c,0,0)arenot presentwheneverv=0.

3. Casestudy:adaptivemotioncontrollerofAutonomousTransportVehicles

In thissection, we illustrate the features of our approach by means ofan exampleadapted from[29]: a model ofa motioncontrollerof

Autonomous Transport Vehicles (ATVs) in

asmartairport.

ATVs are responsible forthe transport of passengers betweenstopovers likepassenger entrances, check-in desks, de-parturegates,andplane parkingpositions.Intheairportthereare twotypesofroadsthattheATVscan use:mainroads andsecondary roads,the latteronesusedduring traffic peaks.ATVscan travel atdifferentspeed inanyroad,preferably not atthemaximumspeed onsecondary roads,asthey arenarrowerthan themain ones.Forsimplicity,we modelonly thesubcomponentofATVsthatcontrolsthevehiclespeedandtheswitchingbetweenmainandsecondaryroads.The S

[

B

]

approachwill beused tospecifyandimplementtheadaptation featuresof thiscontrollerincaseoftraffic congestionor blockages.

3.1. Behavioural level

ThebehaviouralleveldescribesallthecapabilitiesoftheATVcontroller,i.e.alltheactionsthatthesystemisabletodo inanunconstrainedscenario.Wesuppose thateachATVcontrollerhasthepossibilitytoperceivethecurrentsituationof trafficcongestionorblockagebyusingasensororbycommunicatingwithaglobalmonitoringsystemsoftheairport.The ATVcontrollermay,basedonthisperception,decidewhichactiontoexecute.

The usual wayof abstractly specifying a behaviour ofthis kind is a two-phase cycle: in the first phase there is the

perception of theglobalenvironment,onlyrelativelytothecurrentcongestionsituation;inthesecondphase,alocal

action

canbeexecuted,correspondingtochangeeitherthevehiclevelocityortheroadtodrive.

Toformalisethebehaviourallevel B we considerthefollowingsetofobservablevariablesandassociatedsorts:

r

: {

M (main)

,

S (secondary)

}

,thecurrentroad;

v

: {

0 (slow)

,

1 (medium)

,

2 (high)

}

,thecurrentvelocityofthevehicle;

c

: {

true (congestion)

,

false (no congestion)

}

,abooleanvariableindicating thecurrentknowledgeoftheATVcontroller aboutthetrafficcongestion;

p

: {

true (perception)

,

false (no perception)

}

,abooleanvariableindicatingwhetherornottheATVcontrolleriscurrently perceivingthecongestionsituation,i.e.itisinthefirstphaseofitscycle;and

a

: {

true (action)

,

false (no action)

}

,abooleanvariableindicatingwhetherornottheATVcontrolleriscurrentlyexecuting anaction,i.e.itisinthesecondphaseofitscycle.

Hereafter,each state

q of

the B level willbe identifiedbythevaluesoftheobservables,

q

= (

r

,

v

,

c

,

p

,

a

)

.Wewill denote thebooleanvalue

true with

theinteger1 andthebooleanvalue

false with

theinteger0.

Fig. 2 contains a schemarepresentingthe portionof thestate machine, corresponding tothe B level, starting froma genericstate

(

r

,

v

,

c

,

0

,

0

)

,i.e.astate inwhichthecontrollerisatthebeginningofoneiterationofits cycle.Thetwo out-goingtransitionsnon-deterministicallymodeltheperceptionofthesamecongestionsituationknownatthelastperception (state

(

r

,

v

,

c

,

1

,

0

)

)orofthe new(negated)situation(state

(

r

,

v

,

¬

c

,

1

,

0

)

).Inanycase, thesystemproceedsto theaction phase (states

(

r

,

v

,

c

,

0

,

1

)

or

(

r

,

v

,

¬

c

,

0

,

1

)

) where it can decide to changeroad or to change velocity ending up in an updatedstate,readytostartanotherperception–actioniteration.

(6)

Fig. 3. Twopossiblestructurallevels,S0(a)andS1(b),forthemotioncontrollerexample.Theymodeltheadaptationlogicbetweentwomodesofoperation,

r0(normal,blue)andr1(fallback,red).(Forinterpretationofthereferencestocolourinthisfigurelegend,thereaderisreferredtothewebversionofthis

article.)

3.2. Structural level

The structurallevel can be used to give an abstract,constraint-based, specification of thepossible ways (the various statesin S) inwhichthesystemcanfunctiontogetherwiththeadmissibleadaptations amongthem(thetransitionsinS).

Inthiscasestudyweshowhowtoimplement,asan S

[

B

]

system,apolicyofthesmartairportthatrequirestheadaptation ofthe behavioursofthe vehiclesduring theirfunctioning. Weassume thatsome oftheATVsintheairport areequipped withadaptabilitycapabilitiesinordertoimplement, asan example,thefollowingpolicy:“whenever

there is congestion, the

adaptive ATV will have to switch as soon as possible to a secondary road and to limit the velocity to the maximum value 1; on the contrary, whenever there is not congestion, the adaptive ATV will have to use a main road at any velocity”.

ThispolicyclearlyidentifiestwomodesofoperationsoftheadaptiveATVs,whichareactivatedbydifferent environmen-talconditions:

a normal mode of operation, occurring when there is no traffic congestion and such that the main road is driven (r

==

M); and

afallbackmode,occurringwhencongestionoccurs;inthiscasetheATVhastobeinthesecondaryroad(r

==

S) and itcannotdriveatthemaximumvelocity(v iseither0 or1).

These twomodesare modelledby twodifferent S states, asshowninFig. 3(a).The constraintcharacterising thenormal mode(state

r

0)isthedisjunctionofthedescriptionofthemode(

¬

c

r

==

M) withthepossibilityfortheATVcontroller

to perceive theoccurrence ofa congestionwhenin themode (c

r

==

M

p). Notethat without thelatter disjunctive termit wouldnotbe possibleforthesystemto perceivethe differentvalueofthe variable

c because

thatwouldviolate the constraintdescribing the mode (

¬

c

r

==

M), puttingthe perception state out ofthe normalmode. Thisaccording to the semantics of S

[

B

]

(see Section 4). The fallback mode (state r1) is also described, for the same reasons, by the

disjunction ofthe mode description (c

r

==

S

v

<

2) andthe possibilityfor thesystem toperceive

¬

c when in the mode(

¬

c

r

==

S

v

<

2

p).

Theinvariantconditionsonthetransitionsbetween

r

0and

r

1areneededtoavoidtheperceptionofavalueof

c different

fromthatofthemodetowhichthesystemisadaptingto.Forinstance,whenadaptingfrom

r

0to

r

1thetargetsteadystate

isoneinwhichthereiscongestion. Duringtheadaptationweneedtoensurethat,wheneverthereisperception,onlythe value

c can

be perceived,rulingouttheother possibility(duetonon-determinism)ofperceiving

¬

c. Thisisexpressedby theinvariant

(

p

c

)

∨¬

p that, infact,correspondstoforcingthe

S

[

B

]

systemtoignorepossiblechangesintheenvironment during adaptation.Withouttheseinvariants(seeFig. 3(b)),thesystemcouldfallina livelockduring theadaptationphase, asitisshowninSection5.1.

Fig. 4 shows thefull B level where theblue boxencloses thestates satisfyingtheconstraints of

r

0,andthe red box

thosesatisfyingtheconstraintsof

r

1.

4. OperationalsemanticsoftheflatS

[

B

]

system

We give the operational semantics of an S

[

B

]

system asa transition systemresulting from the flattening of the be-haviouralandthestructurallevels.WeobtainaLabelledTransitionSystem(LTS)overstatesoftheform

(

q

,

r

,

ρ

)

,where:

q

Q and r

R are theactive

B state

and S state, respectively;and

ρ

keepsthetarget S state thatmustbereachedduringadaptationandtheinvariantthatmustbefulfilledduringthis phase. Therefore

ρ

iseitherempty (noadaptation isoccurring),ora singleton

{(ψ,

r

)

}

,with

ψ

∈ (,

A

)

aformula and

r

R an S state.

Definition6

(Flat S

[

B

]

system). Consideran S

[

B

]

system.Thecorrespondingflat

S

[

B

]

systemistheLTS

F(

S

[

B

])

= (

F

,

f

0

,

−→

r

r,ψ,r

(7)

Fig. 4. Thebehaviouralstatemachinefor themotioncontrolexample.Eachstateislabelledwiththedifferent evaluationoftheobservable variables

(r,v,c,p,a),i.e.(road,velocity,congestion,perception,action).ColouredareasareusedtorepresentthestatesoftheS levelsofFig. 3(a)and 3(b),which identifystableregionsintheB level.Thesearer0(normalmode,bluebox)andr1(fallback/congestionmode,redbox).(Forinterpretationofthereferences

tocolourinthisfigurelegend,thereaderisreferredtothewebversionofthisarticle.)

F

=

Q

×

R

× ({(ψ,

r

)

| ∃

r

R

.

r

−→S

ψ r

}

∪ {∅})

isthesetofstates;

f0

= (

q0

,

r0

,

∅)

istheinitialstate;

−→⊆

r

F

×

F , with

r

R, isafamilyoftransitionrelationsbetweennon-adaptingstates,i.e.,bothsatisfying

L

(

r

)

;

r,ψ,r

−−−−→⊆

F

×

F , with

r

,

r

R and

ψ

∈ (,

A

)

,isafamilyoftransitionrelations betweenadapting states,wherethe adaptationisdeterminedbythe S transition r

−→S

ψ r ;and

thepairsin

−→

r andin

−−−−→

r,ψ,r areallandonlythosederivableusingtherulesinTable 1. LetusdiscusstheruleslistedinTable 1characterisingtheflattenedtransitionalsemantics:

Rule Steady describesthe steady(i.e. non-adapting)behaviour of thesystem. Ifthe systemisnot adapting anda B

state

q can

performa transitionto a

q

thatsatisfiesthecurrentconstraints L

(

r

)

,thentheflat systemcan performa non-adaptingtransition

−→

r oftheform

(

q

,

r

,

∅)

−→ (

r q

,

r

,

∅)

.

Rule AdaptStart regulatesthestartingofanadaptationphase.

Adaptationoccurswhen allof thenext B states do notsatisfy the current S state constraints—i.e.

q

.(

q

→B

q

q

|

L

(

r

))

—andthe

B machine

isnotitselfdeadlocked(q

→B

q ).Inthiscase,foreach

S transition r

−→S

ψ r an adapta-tiontowardsthetargetstate

r

,undertheinvariant

ψ

,canstart.Theflatsystemperformsanadaptingtransition

−−−−→

r,ψ,r oftheform

(

q

,

r

,

∅)

−−−−→ (

r,ψ,r q

,

r

,

{(ψ,

r

)

})

.

Rule Adapt can be usedonly during an adaptation phase.It handles the casein which,after thecurrent transition, the systemkeepsadapting because a steadyconfiguration cannot be reached(

q

.(

q

→B

q

q

|

L

(

r

))

). In this situation,sincethesystemstill mustadapt(q

|

L

(

r

)

),ifthe B machine isnotdeadlockedandtheinvariantcan still be satisfied(q

→B

q andq

| ψ

),the ruleallows atransitionofthe form

(

q

,

r

,

{(ψ,

r

)

})

−−−−→ (

r,ψ,r q

,

r

,

{(ψ,

r

)

})

. Note thatduringadaptationthebehaviourisnotregulatedbythe

S states

constraints.Notealsothatthesemanticsdoesnot assurethatastate wherethetarget S state constraintsholdiseventually reached.Twodifferentformulationsofsuch adaptabilityrequirementsaregiveninSection5.

(8)

Table 1

OperationalsemanticsoftheflatS[B]system.

Steady q| L(r) qBq q | L(r) (q,r,∅)−→ (r q ,r,∅) AdaptStart ∀q .(qBq q | L(r)) q| L(r) qBq r ψ −→Sr q | L(r ) q | ψ (q,r,∅)−−−−→ (r,ψ,r q ,r,{(ψ,r )}) Adapt ∀q .(qBq q | L(r )) q| ψ q| L(r ) qBq q | ψ (q,r,{(ψ,r )})−−−−→ (r,ψ,r q ,r,{(ψ,r )}) AdaptEnd q| ψ q| L(r ) qBq q | L(r ) (q,r,{(ψ,r )})−−−−→ (r,ψ,r q ,r ,∅) AdaptStartEnd ∀q .(qBq q | L(r)) q| L(r) qBq r ψ −→Sr q | L(r ) (q,r,∅)−−−−→ (r,ψ,r q ,r ,∅)

Alsorule AdaptEnd canonlybeappliedduringanadaptationphaseandithandlesthecaseinwhich,afterthecurrent transition, theadaptationmustendbecauseasteadyconfigurationhasbeenreached(q

|

L

(

r

)

).Itallowsatransition

r,ψ,r

−−−−→

fromanadaptingstate

(

q

,

r

,

{(ψ,

r

)

})

tothesteady(non-adapting)state

(

q

,

r

,

∅)

.

Rule AdaptStartEnd handles the special case in which an adaptation phase must start from a steady situation—

q

.(

q

→B

q

q

|

L

(

r

)

—but then, after just one move of the B level, another steady region of the S level is reached(q

|

L

(

r

)

).Inthiscasetheinvariant

ψ

associatedtothe S transition isignoredandthesystemgoesdirectly intoanothersteadystate.Notethatthisruleisalternativetotherule AdaptStart inwhichtheinitialsituationisthe same, but the steady region is not reached after one B transition. The flat system performs an adapting transition

r,ψ,r

−−−−→

oftheform

(

q

,

r

,

∅)

−−−−→ (

r,ψ,r q

,

r

,

∅)

.

Therefore,asuccessfuladaptationoccurswhenrules AdaptEnd or AdaptStartEnd canbeapplied,i.e.whenatransition fromanadaptingtoasteadystateisfired.

Letusnowstatesome propertiesofthegivenflatsemantics.Inthefollowing,givenanytransitionrelation

andany state

s,

by

s

andby s



we mean,asusual, thatthereexistsa state s suchthat s

s andthat thereexistsnostate

s suchthat

s

s , respectively.Moreover, by

+ we indicateafinite,non-empty,sequence of

steps;moreformally, there exists

n

∈ N,

n

>

0 suchthat s

=

s0

s1

→ · · ·

sn−1

sn. Finally,by

k,

k

0,we indicate

k consecutive

steps of

therelation

:

s

=

s0

s1

→ · · ·

sk−1

sk.If

k

=

0,then

s

0s isequivalenttosaythatthereistheemptysequenceof

steps

s,

andthus

s

=

s. Thisisalwayspossible,eveniftherelation

isnotreflexive.

Proposition1

(Properties of flat semantics). Let

F(

S

[

B

])

= (

F

,

f

0

,

→ ∪

r

r,ψ,r

−−−→)

be a flat S

[

B

]

system. All the following statements hold:

(i) If

a steady transition can be performed, then adaptation cannot start:

∀(

q

,

r

,

∅)

F

.

(

q

,

r

,

∅)

→ (

r q

,

r

,

∅)

⇒ (

q

,

r

,

∅)

−−−→

r,ψ,r



(ii) If

adaptation can start, then no steady transition is possible:

∀(

q

,

r

,

∅)

F

.

(

q

,

r

,

∅)

−−−→ (

r,ψ,r q

,

r

,

{(ψ,

r

)

})

⇒ (

q

,

r

,

∅)



r (iii) During

adaptation no steady transition is possible:

∀(

q

,

r

,

{(ψ,

r

)

})

F

.

(

q

,

r

,

{(ψ,

r

)

})



r

(iv) The

non-adapting and the adapting transition relations are disjoint:

r

,

r

R

,

∀ψ ∈ (,

A

).

→ ∩

r

−−−→= ∅

r,ψ,r

(v) In

case of a successful adaptation, the adaptation phase ends as soon as possible, i.e. as soon as the target steady state can be

reached with a single transition.

(vi) Given

any q

Q and r

R, then every infinite path πin

F(

S

[

B

])

starting in a state

(

q

,

r

,

∅)

such that q

|

L

(

r

)

is of one of the following kinds:

(1) adaptation always succeeds; the path alternates between steady transitions and adaptation paths:

π

= (

q

=

q0

,

r

=

r0

,

∅)(

r0

−→)

m0

(

−−−−−→)

r0,ψ0,r1 n0

· · ·

· · · (

qi

,

ri

,

∅)(

ri

→)

mi

(

−−−−−→)

ri,ψi,ri+1 ni

(

q i+1

,

ri+1

,

∅) · · ·

(9)

(2) adaptation lasts forever; the path has a prefix in which steady transitions and adaptation paths alternate, but then one adaptation path never stops:

π

= (

q

=

q0

,

r

=

r0

,

∅)(

r0

−→)

m0

(

−−−−−→)

r0,ψ0,r1 n0

· · ·

· · · (

qi

,

ri

,

∅)(

ri

→)

mi

(

ri,ψi,ri+1

−−−−−→)

ni

(

q i+1

,

ri+1

,

∅) · · ·

· · · (

qk

,

rk

,

∅)

rk,ψk,rk+1

−−−−−−→ (

qk+1

,

rk

,

k

,

rk+1

})

rk,ψk,rk+1

−−−−−−→ (

qk+2

,

rk

,

k

,

rk+1

})

rk,ψk,rk+1

−−−−−−→ · · ·

where k

0 and

for each i,

0

i

<

k, either mi

=

1

ni

=

0 or

m

i

=

0

ni

>

0.

(vii) Let

π

F(

S

[

B

])

be an infinite path starting in a state

(

q

,

r

,

∅)

such that q

|

L

(

r

)

. Then, in every position i of the path such that

π

[

i

]

= (

qi

,

ri

,

∅)

, it holds qi

|

L

(

ri

)

.

Proof. See AppendixA.1

2

4.1. Termination

In an S

[

B

]

system, deadlockscannot be compatiblewithadaptability. Indeed,we see adaptabilityasthe propertyfor whichasystem

continuously operates

understable,allowedmodes(steadystates),bypossiblyperformingadaptationpaths acrossmodes.

Intheflatsemanticsdeadlocksoccurringatadaptingstates,e.g.whentheadaptationinvariantcannotbemet,areclearly conflictingwiththeconceptofadaptability.Instead,deadlocksatsteadystatesaremoresubtletointerpret,sincetheymay occurundertwodifferentconditions:

fromthecurrentstate,anytransitionleadtoastateviolatingthecurrentconstraints,and,atthesametime,adaptation cannotstartbecausenoneofthenext

B states

meetanyoftheadaptationinvariantsandanyofthetargetconstraints. Inotherwords,theflatsemanticsterminatesevenifthe

B level

canproceed.Evidently,thisviolatesadaptability.

the B level cannot progress atall. Weconsider thissituationasa bad deadlock state inthebehavioural model. Con-versely,every

B state

indicatinga

good termination should

havethechancetoprogressandthereforemustbemodelled, asusualinthiscase,withanidlingself-loop.

Wecapturetherequirementforwhichtheflat S

[

B

]

mustnotterminatethroughtheProgress

(

q

,

r

)

predicate: Progress

(

q

,

r

)

⇐⇒ (

q

,

r

,

∅)

→ ∨ (

r q

,

r

,

∅)

r,ψ,r

−−−→

4.2. Flat semantics of the motion control example

Theflatsemanticsofthetwosystems

S

0

[

B

]

and

S

1

[

B

]

implementingtheATVmotioncontrollercasestudyaredepicted

inFigs. 5 and 6,respectively.

Notably,the samebehaviourallevel B possesses differentadaptation capabilitiesdepending onthestructure S that is considered. Indeed,in

F(

S0

[

B

])

every adaptation pathleads to a target S state. Onthe other hand,in

F(

S1

[

B

])

always

thereexistsanadaptationpathleading toatargetstableregion,butitmaycontaincyclesofadaptingstates,thus leading topossiblyinfiniteadaptationpaths.

Inother words,thebehaviourallevel

B is

abletosuccessfullyadaptunderthestructurallevel S0,for

all possible

adapta-tion paths. RecallingthedefinitionsintroducedinSection1,

S

0

[

B

]

is

strongly adaptable.

Conversely,

B is

abletosuccessfully

adaptunderS1 onlyfor

some adaptation paths,

i.e.thefiniteones. Therefore,S1

[

B

]

is

weakly adaptable.

Thesetwodifferent

kindsofadaptabilityareformalised inSection5.

5. Adaptabilityproperties

ThetransitionalsemanticsintroducedinSection4doesnotguaranteethatanadaptationphasecanalwaysstartorthat, oncestarted, it alwaysends up inastate satisfyingthe constraintsofthetarget S state. In thissectionwe wantto give someformaltoolstoanalyseagivensystemw.r.t.thesekindofproperties.Asafirststep,wecharacterisetwoadaptability notionsby meansoftwo relationsoverthe setof B states andthesetof S states, namelya

weak adaptation relation

R

w

anda strong adaptation relation

R

s.Then, wecharacterise the sameadaptabilitynotions logicallyandweprove that they

canbemodelcheckedbyusingproperformulaeofatemporallogic.

Informally,astate

q of

B is weakly adaptable to astate

r of

S if itsatisfiestheconstraintsimposedby

r and

someofits successorsareeitherweakly adaptabletothesame

r or

thereisanadaptationphaseoftheflatsystemthat,from

q,

reaches astate

q

thatisweakly adaptabletoanotherS state r .Inotherwords,werequirethatstatessatisfying

L

(

r

)

areinrelation

(10)

Fig. 5. The flat semantics of the system S0[B]. Here, every adaptation path leads to a target S-state.

with

r and

that from“border”states,thatisto saythosethatcanstart anadaptationphase forleaving

r,

thereisalways at leastonewayto safelyreachanothersteadysituation inanother S state r .Asexplained inSection 4.1, theProgress predicateisused toruleout steadyconfigurationsina stateofbad termination. Weformally definethisrelationusinga co-inductivestyleasitisusuallydone,forinstance,forbisimulationrelations.

(11)

Fig. 6. TheflatsemanticsofthesystemS1[B].Inthiscase,thereareadaptationpathsleadingtoatargetstableregion,butalsoinfiniteadaptationpaths

duetocycles(seee.g.theadaptationpathfromr0tor1(M,2,1,0,1)→ (S,2,1,0,0)→ (S,2,0,1,0)→ (S,2,0,0,1)→ (M,2,0,0,0)→ (M,2,1,1,0)(M,2,1,0,1)).

Definition7 (Weak adaptation). Given an S

[

B

]

system, a binary relation

R

Q

×

R is a weak adaptation if and only if

whenever

q

R

r we

have:

(i) q

|

L

(

r

)

andProgress

(

q

,

r

)

,

and

(12)

(iii) if

(

q

,

r

,

∅)

−−−−→

r,ψ ,r for some

ψ

∈ (,

A

)

and r

R then there exist q

Q

,

ψ

∈ (,

A

)

andr

R such that

(

q

,

r

,

∅)

−−−−→

r,ψ,r +

(

q

,

r

,

∅)

and

q

R

r .

Wesaythatastate

q

Q is weakly adaptable to astate

r

R, written

q

|w

r, ifandonlyifthereisaweakadaptationrelation

R

suchthat

(

q

,

r

)

isin

R

.

Atthelevelofthewholesystem,wesaythat

S

[

B

]

is

weakly adaptable if

theinitial

B state q

0isweakly adaptabletothe

initial

S state r

0.

Proposition2(Union of weak adaptation relations). Given an S

[

B

]

system, if

R

1and

R

2are weak adaptation relations, then

R

1

R

2

is a weak adaptation relation.

Proof. See AppendixA.2

2

Definition8

(Weak adaptability).

Givenan S

[

B

]

system,theunionofallweakadaptationrelationsamongthestatesQ and

R of S

[

B

]

isdenotedby

R

w andisthe

weak adaptability relation

of

S

[

B

]

.

Lemma1

(Propagation of weak adaptation relation). Consider an S

[

B

]

system and let q and r be such that q

|w

r. Then there exists in

F(

S

[

B

])

an infinite path

π

= (

q

=

q0

,

r

=

r0

,

∅)(

−→)

r0 m0

(

−−−−−→)

r0,ψ0,r1 n0

· · ·

· · · (

qi

,

ri

,

∅)(

ri

→)

mi

(

−−−−−→)

ri,ψi,ri+1 ni

(

q i+1

,

ri+1

,

∅) · · ·

such that

i

0

.

q

i|wri

∧ ((

mi

=

1

ni

=

0

)

∨ (

mi

=

0

ni

>

0

))

.

Proof. See AppendixA.3

2

Weakadaptabilityguaranteesthatthereisalwaysatleastonewayforacertainstateofan S

[

B

]

systemtoadapt,thatis tosaytocontinuetoevolveinaconsistentwayw.r.t.thestructuralconstraintsofthe

S level.

Astrongerpropertythatcould beusefultoknowabouttheadaptabilityofasystemiswhatwecall

strong adaptability.

A B state q is strongly adaptable to

an S state r if itsatisfiestheconstraintsimposedby

r and

allitssuccessors

q

areeitherstrongly adaptabletothesame

r

ortheyarealwaysthestartingpointofasuccessfuladaptationphasetowardsstates

q

thatarestrongly adaptabletoother

S states. Again,bad deadlocksare excluded fromthe relations.Thistime we requirethat all the“border” statesare safe doorstoothersteadysituations,whateverpathistakenfromthem.

Definition9

(Strong adaptation).

Givenan S

[

B

]

system, a binary relation

R

Q

×

R is a strong adaptation if and onlyif

whenever

q

R

r we have:

(i) q

|

L

(

r

)

andProgress

(

q

,

r

)

,

and

(ii) forall

q

Q , if

(

q

,

r

,

∅)

−→ (

r q

,

r

,

∅)

then

q

R

r, and

(iii) alladaptationpathsstartingfrom

(

q

,

r

,

∅)

arefiniteandendupinastate

(

q

,

r

,

∅)

suchthat

q

R

r

.

We say that a state q

Q is strongly adaptable to a state r

R, written q

|s

r, if andonly ifthere is a strong adaptation relation

R

suchthat

(

q

,

r

)

isin

R

.

Atthelevelofthewholesystem,wesaythat

B is strongly adaptable to S if

theinitial B state q0 isstrongly adaptableto

theinitial S state r0.

Proposition3

(Union of strong adaptation relations). Given an

S

[

B

]

system, if

R

1 and

R

2 are strong adaptation relations, then

R

1

R

2is a strong adaptation relation.

Proof. Asinthecaseofweakadaptationrelations.

2

Definition10 (Strong adaptability). Givenan S

[

B

]

system, theunionofall strongadaptationrelations amongthe states Q

and

R of S

[

B

]

isdenotedby

R

sandisthe

strong adaptability relation

ofS

[

B

]

.

Intheremainderofthepaperwewillalternativelysaythatan S

[

B

]

systemisweakly (strongly)adaptable,inthesense that B is weakly (strongly) adaptableto S. Itis straightforwardto seethat strongadaptabilityimpliesweak adaptability, sincethestrongversionoftherelationrequiresthateveryadaptationpathreachesatarget

S state,

whiletheweakversion justrequiresthatatleastoneadaptationpathreachesatarget S state.

(13)

Proposition4

(Strong adaptation implies weak adaptation). Consider an S

[

B

]

system and let q and r be such that q

|s

r. Then, it holds q

|w

r.

Proof. See AppendixA.4

2

Giventheflatsemantics

F(

S

[

B

])

= (

F

,

f

0

,

−→ ∪

r r,ψ,r

−−−−→)

ofan S

[

B

]

system, wewilldenote,inthefollowing,thesetof reachable statesfroma certainstate f

F as the reflexiveandtransitive closurePost

(

f

)

of theoperator Post

(

s

)

= {

s

F

|

(

s

,

s

)

−→ ∪

r

−−−−→}

r,ψ,r .

Lemma2

(Propagation of strong adaptation relation). Consider an S

[

B

]

system and let q and r be such that q

|s

r. Then, every state

(

q

,

r

,

∅)

Post

((

q

,

r

,

∅))

is such that q

|s

r .

Proof. See AppendixA.5

2

Thefollowingpropositiongivesaprecisecandidaterelationforcheckingifasystemisstrongly adaptable:sucha candi-dateisdeterminedbythesteadystatesoftheflatsemanticsthatarereachablefromtheinitialstate.

Proposition5

(Construction of strong adaptation relation). Given an

S

[

B

]

system, let

F(

S

[

B

])

= (

F

,

f

0

,

→ ∪

r

r,ψ,r

−−−→)

be its flat semantics. Then S

[

B

]

is strongly adaptable if and only if

R

= {(

q

,

r

)

Q

×

R

| (

q

,

r

,

∅)

Post

(

f0

)

}

is a strong adaptation relation.

Proof. See AppendixA.6

2

5.1. Adaptation relations in the motion controller example

Inthefollowingwe willshowthat inthe ATVmotioncontrollercasestudy S0

[

B

]

isstrongly adaptable(andthusalso

weakly adaptable)and

S

1

[

B

]

isweakly adaptable,butnotstrongly adaptable.

Inordertoverifythat S0

[

B

]

isstrongly adaptable, weneedtoprovethat

q

0

|s

r0,byfindingastrongadaptationrelation

R

s.t.

(

q0

,

r0

)

R

.Notethatin

F(

S0

[

B

])

,everystateisreachablefromtheinitialstate

(

0

,

r0

,

∅)

.ThereforebyProposition 5,

weconsidertherelation

R

= {(

q

,

r

)

|

q

Q

,

r

R

,

(

q

,

r

,

∅)

F

}

,where F is thesetofflatstatesof

F(

S0

[

B

])

.Itiseasyto

verifythat

∀(

q

,

r

)

R.

q

|

L

(

r

)

;andthatProgress

(

q

,

r

)

holdsforanyofsuchstates,becausetherearenodeadlockstates intheflatsemantics.Thereforecondition (i)ofthedefinitionofstrongadaptationisalwaystrueandhasnottobefurther checked.Clearly,

(

q0

,

r0

)

R

.Finally,itcanbeshownthatrequirements(ii)and(iii)ofDefinition 9holdforeachelement

of

R

.

Weshowtheprooffor

((

M

,

0

,

0

,

0

,

0

),

r0

)

and

((

M

,

0

,

1

,

1

,

0

),

r0

)

.Theotherpairscanbeprovedanalogously.

• ((

M

,

0

,

0

,

0

,

0

),

r0

)

(ii)

((

M

,

0

,

0

,

0

,

0

),

r0

,

∅)

r0

−−→ ((

M

,

0

,

0

,

1

,

0

),

r0

,

∅)

and

((

M

,

0

,

0

,

1

,

0

),

r0

)

R

;

((

M

,

0

,

0

,

0

,

0

),

r0

,

∅)

−−→ ((

r0 M

,

0

,

1

,

1

,

0

),

r0

,

∅)

and

((

M

,

0

,

1

,

1

,

0

),

r0

)

R

(iii)

((

M

,

0

,

0

,

0

,

0

),

r0

,

∅)

r,ψ,r

−−−−→



• ((

M

,

0

,

1

,

1

,

0

),

r0

)

(ii)

((

M

,

0

,

1

,

1

,

0

),

r0

,

∅)



−→

r

(iii) thereisonlyoneadaptationpathfrom

((

M

,

0

,

1

,

1

,

0

),

r0

,

∅)

leadingtotheflatstate

((

S

,

0

,

1

,

0

,

0

),

r1

,

∅)

(through

theB state

(

M

,

0

,

1

,

0

,

1

)

),and

((

S

,

0

,

1

,

0

,

0

),

r1

)

R

.

On the other hand, we demonstrate that S1

[

B

]

is weakly adaptable by finding a weak adaptation relation

R

s.t.

(

q0

,

r0

)

R

.Wetakeas

R

thefollowingrelation:

{((

M

,

0

,

0

,

0

,

0

),

r0

), ((

S

,

0

,

1

,

0

,

0

),

r1

), ((

M

,

0

,

1

,

1

,

0

),

r0

), ((

S

,

0

,

0

,

1

,

0

),

r1

)

}

Similarly to S0

[

B

]

,

(

q0

,

r0

)

R

andfor all

(

q

,

r

)

R

, q

|

L

(

r

)

and Progress

(

q

,

r

)

both holds. Thus, we need to check requirements(ii)and(iii)ofDefinition 7toprovethat

R

isaweakadaptationrelation.

Weobservethatpairs

((

M

,

0

,

0

,

0

,

0

),

r0

)

and

((

S

,

0

,

1

,

0

,

0

),

r1

)

meetrequirements(ii)and(iii),thelatterbeingtrivially

verified since they do not admit adaptation transitions.Pairs

((

M

,

0

,

1

,

1

,

0

),

r0

)

and

((

S

,

0

,

0

,

1

,

0

),

r1

)

also comply with

theweak adaptation definition,sincethey can bothreach,in afinite numberofadaptationsteps, flatstates thatmap to elementsin

R

,i.e.

((

S

,

0

,

1

,

0

,

0

),

r1

)

and

((

M

,

0

,

0

,

0

,

0

),

r0

)

,respectively.

However,notethat

((

S

,

0

,

1

,

0

,

0

),

r1

)

cannotbeinanystrongadaptationrelationbecause,bythepropagationproperty,

((

M

,

2

,

1

,

1

,

0

),

r0

)

wouldbeintherelationandthereareinfiniteadaptationpathsstartingfromitscorrespondingflatstate

Figura

Fig. 1. Adaptation loop in an S [ B ] system. At each step, S observes B and decide if there is a need to change state
Fig. 2. A schema of states and transitions starting from a generic state ( r , v , c , 0 , 0 )
Fig. 3. Two possible structural levels, S 0 (a) and S 1 (b), for the motion controller example
Fig. 4. The behavioural state machine for the motion control example. Each state is labelled with the different evaluation of the observable variables
+3

Riferimenti

Documenti correlati

The aim of the research is to substantiate methods of increasing the adaptability of vehicles to variable low-temperature operating conditions based on a neural control system

It is submitted that the probable intention of the drafters of the Restatement (Second) was to achieve a balance (in section 187 (2) (a)) between the older reasonable

Ad oggi sono 36 gli stati americani che hanno emanato, o hanno in corso di approvazione, normative sul tema del divieto per i datori di lavoro di richiedere i dati personali

Quale concetto “ampio”, la nozione di adaptability include quindi non solo il significato di flessibilità in termini di retribuzione e rapporti di lavoro, ma anche la

Il luogo di lavoro agile (agile workplace) di Unilever si focalizza su tre aree – practice (diffondere e praticare il più possibile la nuova modalità di svolgere il lavoro

Come riportato nella tabella sottostante, le quattro aree citate possono essere cosi descritte: nell’area sociale, il focus è stato posto sullo sviluppo delle relazioni

Il sindacato ha poi compreso che la maggior parte dei lavoratori autonomi non aveva intenzione ad essere assimilata al lavoro dipendente, auspoicando lo sviluppo di diverse

Two methods are used to measure the tt production cross section. The reference method is a binned likelihood fit to multi-differential final state distributions, performed in