• No results found

Optimal Control for Multi-Mode Systems with Discrete Costs

N/A
N/A
Protected

Academic year: 2022

Share "Optimal Control for Multi-Mode Systems with Discrete Costs"

Copied!
49
0
0

Loading.... (view fulltext now)

Full text

(1)

Optimal Control for Multi-Mode Systems with Discrete Costs

Dominik Wojtczak

University of Liverpool AVeRTS workshop

14th July 2017

(based on joint work with Mahmoud A. Mousa and Sven Schewe)

(2)

Hybrid Automata

They consist of

A finite state transition system

Differential equations in each control state

Example

Linear Hybrid Automata

(3)

+overlapping invariants

SPDI* 2-dim initialized

rectangular automata*

2-dim TA*

PCD2m

or stop-watches*

linear resets*

3-dim TA +comparative guards*, 3-dim uninitialized* or

3-dim PCD*

HPCD1c, HPCD1, HPCDx

HPCDf n/zeno int

2-dim HPCDzeno non-rectangular*

automata 1-dim oPAM

1-dim PAMpow

2-dim PAM*

2-dim PCD*

OPEN 2-dim HPCD

+overlapping invariants +comparative guards 1-dim PAM*

+overlapping invariants +comparative guards +constant resets

+non-overlapping invariants +linear resets

+comparative guards

+non-overlapping invariants +comparative guards

PAMreg*

+translational resets

DECIDABLE

UNDECIDABLE

+uninitialized

Figure 1: Decidable, open and undecidable subclasses of hybrid systems (unstarred results are contributions of this paper).

that slight extensions of the 2-dim HPCD class lead to the undecidability of the reachability question. We present a partially correct but not necessarily terminating algorithm for testing reachability in 1-dim PAMs, and show how decidable subclasses can be identified in section 5. In section 6, we present related work, and we conclude in the last section.

2. Preliminaries

In this section we define several classes of hybrid automata, two dimensional manifolds, and our reference models: PAMs and Minsky machines.

2.1. Hybrid Automata

There are many equivalent definitions of hybrid systems [10, 4, 11]. Con- ceptually, a hybrid automaton is a directed graph of discrete states and tran- sitions, augmented with several real-valued continuous variables, which allows arbitrary: (1) Invariant expressions dictating when (for which values of vari- ables) the system can stay in each discrete state; (2) Di↵erential equations in the flow expressions in each discrete state (continuous evolution of variables with time); (3) Conditions controlling when a transition can be taken, in the guard expressions; (4) Equations that change the values of the variables, in the reset expressions during each discrete state transition (instantaneous discrete evolu- tion). A computation of a hybrid automaton is a series of continuous evolution steps of arbitrary time-length each, interspersed with an arbitrary number of zero time-length discrete transition steps.

Definition 2.1. Ann-dimensional hybrid automatonis a tupleH= (X, Q, f,I0, Inv, )where

• X ✓ Rn is the continuous state space. Elements of X are written as x= (x1, x2, . . . , xn), we always use variablesx1, x2, . . . , xnto denote com- ponents of the state vector;

(4)

Multi-mode Systems: Safe Schedulability

˙ x=2

˙ y= 3

m1

˙ x=1

˙ y=−1

m2

˙ x=1

˙ y=−1

m2

˙ x=1

˙ y= 3

m3

˙ x=1

˙ y= 3

m3

˙ x= 2

˙ y=−2

m4

˙ x= 2

˙ y=−2

m4

˙ x= 2

˙ y=−1

m5

˙ x= 2

˙ y= 3

m6

Safe set: x∈[65,70], y∈[65,70]

68 68 x y

s0

67 67 s1

(m2,1) 66

70 s2

(m3,1) 68

68 s3

(m4,1) 67

67 s4

(m2,1) · · ·

Keywords: modes, schedule, run, and safe schedule

(5)

Multi-mode System: Zeno schedule

˙ x=2

˙ y= 3

m1

˙ x=1

˙ y=−1

m2

˙ x=1

˙ y= 3

m3

˙ x= 2

˙ y=−2

m4

˙ x= 2

˙ y=−1

m5

˙ x= 2

˙ y= 3

m6

Safe set: x∈[65,70], y∈[65,70]

68 68 x y

s0

68 68 s1

(m2,0) 68

68 s2

(m3,0) 68

68 s3

(m4,0) 68

68 s4

(m2,0) · · ·

Keywords: Zeno Schedule

(6)

Multi-mode Systems: Zeno schedule

˙ x=2

˙ y= 3

m1

˙ x=1

˙ y=1

m2

˙ x=1

˙ y= 3

m3

˙ x= 2

˙ y=−2

m4

˙ x= 2

˙ y=−1

m5

˙ x= 2

˙ y= 3

m6

Safe set: x∈[65,70], y∈[65,70]

68 68 x y

s0

67 67 s1

(m2,1) 66.5

68.5 s2

(m3,12) 67

68 s3

(m4,14) 66.875 67.875

s4

(m2,18) · · ·

Keyword: Zeno Schedule

(7)

Formal Definition

Definition (Constant-Rate Multi-Mode Systems: MMS)

A MMS is a tupleH= (M, N, R)where – M is a finite nonempty set ofmodes, – N is the number of continuous variables,

– R:M →RN gives for each mode therate vector, – S⊆RN is abounded convex set ofsafe states.

– Therunof a scheduleh(m1, t1),(m2, t2), . . . ,(mk, tk)ifroms0is s0,(m1, t1), s1, . . . ,(mk, tk), sk

such thatsi=si−1+ti·R(mi)for all for all1≤i≤k.

– Ascheduleσis safe ats0 if all states of the run ofσfroms0are safe (i.e.,∈S).

(8)

Problems Studied and Results

Safe Schedulability Problem

Given an MMSHand a starting states0 decide whether there exists a non-Zeno safe schedule.

Theorem (Alur, Trivedi, W. (HSCC 2012))

Safe Schedulability can be solved inpolynomial timefor polytopes.

Safe Reachability Problem

Given an MMSH, astarting state s0∈S, and atarget statest∈S, decide whether there exists a safe schedule that reachesstfroms0.

Theorem (Alur, Trivedi, W. (HSCC 2012))

Safe Reachability can be solved inpolynomial timeif the starting and the target states lie in the interior of the polytopeS.

(9)

Safe Schedulability Problem: Geometry

˙ x=2

˙ y= 3

m1

˙ x=1

˙ y=1

m2

˙ x=1

˙ y= 3

m3

˙ x= 2

˙ y=2

m4

˙ x= 2

˙ y=1

m5

˙ x= 2

˙ y= 3

m6

Safe set: x∈[65,70], y∈[65,70]

m1

(−2,3)

m4

(2,−2) m6

(2,3)

m2 (−1,−1)

m3

(−1,3)

m5

(2,−1)

(10)

Safe Schedulability Problem: Geometry

s1

m6

m3

m1

m2 m4

m5

s1

m6

m3

m1

m2 m4

m5

s1

m6

m3

m1

m2 m4

m5

s1

m6

m3

m1

m2 m4

m5

s2

s1

m6

m3

m1

m2

m4

m5

s2 s3

s4

m5

(11)

Reachability Problem: Geometry

s1

m6

m3

m1

m2 m4

m5

s5

s2

m6

m3

m1

m2 m4

m5

s3

s1 s5

(12)

Thumb Rules: Reachability

The following isfeasible:

s0+

|M|

X

i=1

R(i)·ti=st

s0

st

R1

R2

(13)

Reachability: Boundary Case

s 1 s 2 . . .

s s 0

1. Rate vectors are(1,1) and(1,−1) 2. Angle ats0 is30o.

3. ksk, sk=ks, s0k ·(

3−1

3+1)k.

(14)

Schedulability: Boundary Case

Lemma

For any finite safe scheduleσthere exists a finite safe scheduleσ0 s.t.:

1. All modes that were ever safe during the run ofσ will be safe in the final state ofσ0, and

2. The set of safe modes along the run ofσ0 will always be increasing.

x0, y0

x1

x2

x3

y1

y2

y3

σ: t1 t2 t3

σ0: t1/2

t1/4 t2/2

t1/8 t2/4 t3/2

(15)

Algorithm: Boundary Case

1. Compute the sequence of set of modesM1, M2, . . . , Mk such that – M1 is the set of safe modes atx0, and

– Miis the set of safe modes at states reachable fromx0 using only modes fromMi1.

2. M1⊂M2⊂ · · · ⊂Mk.

3. Modes outsideMk can never be used when starting atx0. 4. The setMk can be computed in polynomial time.

5. MMS is schedulable fromx0 if and only if:

X

m∈Mk

R(m)·fm= 0and X

m∈Mk

fm= 1 6. That can, again, be checked in polynomial time.

7. If the system is safe, there exists an ultimately periodic schedule.

(16)

Generalisations and Cost Optimal schedules

Generalisations:

– One can add somestructureto the real-time system by adding – guardson mode-switches

– mode-dependentinvariants

– Both generalisations lead toundecidabilityof the reachability problem.

– Cost per time unit in each mode – the same complexity via similar analysis.

– .... and what about cost per mode switch?

(17)

Multi-mode Systems with Discrete Costs

Definition (Multi-mode system with discrete costs)

MMS with discrete costs is a tupleH= (M, N, R, πc, πd, Vmin, Vmax, V0) where:

– M is a finite set of modes;

– N is the number of continuous variables in the system;

– R:M →QN is the rate of change vector in a given mode;

– πc :M →Q≥0 is the cost per time unit spent in a given mode;

– πd:M →Q≥0 is the cost of switching to a given mode;

– Vmin, Vmax∈QN: Vmin< Vmax, define the safe set,S, as follows {x∈RN :Vmin≤x≤Vmax};

– V0∈QN, such thatV0∈S, defines the initial value of all the variables.

(18)

Costs of Schedules

Thecost of a finite scheduleσ=h(m1, t1),(m2, t2), . . . ,(mk, tk)iis defined asπ(σ) =Pk

i=1πd(mi) +πc(mi)ti and itstime horizonisPk i=1ti.

Finite-time horizon problem

Minimiseπ(σ)among schedulesσwith a given time horizontmax(in binary).

Thelimit-average cost of an infinite schedule σ=h(m1, t1),(m2, t2), . . .iis defined as

πavg(σ) = lim sup

k→∞

k

X

i=1

πd(mi) +πc(mi)ti

! /

k

X

i=1

ti

Infinite-time horizon problem

Minimiseπavg(σ)among all schedules with infinite time horizon.

(19)

Finite-time horizon problem

Observation

A finite-time horizon problem may not have an optimal schedule.

m1

(−1,1)

m2

(1,−1) m3

(1,1)

All costs are0 apart fromπc(m3) = 1.

Scheduleσ= (m3, ), (m1, t),(m2, t)l

, wheret0=tmax−,l=dt0/e, and t=t0/2l, has time horizon tmax and total cost >0.

(20)

Finite-time horizon problem

Lemma

There exists an-optimal safe schedule of an exponential length.

Proof (sketch)

1. Remove all modes that can never be used by a safe schedule fromV0

using a similar procedure as in the boundary case for the schedulability problem.

2. Find an easy target state with time horizontmax:

– minimum number of coefficients at the border usingO(N)LP queries;

– sufficiently far away from the border using another LP.

3. Split the problem into reaching the mid-point of this schedule by considering−H.

4. All safe modes atV0 are safe at this mid-point, which makes it easier to reach.

(21)

Finite-time horizon problem

Theorem

Checking for the existence of an-optimal safe schedule with cost at mostC is inNExpTime.

Proof (sketch)

1. Guess the order of modes used in an -optimal safe schedule.

2. Write down an exponentially sized LP where the duration of each timed action is a separate variable.

3. Check for the existence of a safe schedule and its minimal total cost.

4. Compare this cost withC.

Theorem

Checking for the existence of an-optimal-safeschedule with cost at mostC is inPSpace.

Proof (sketch)

We can guess on the fly the modes and intermediate points along the schedule

(22)

Infinite-time horizon problem

However, we know more about the 1-dimensional case.

Theorem

An optimal safe infinite schedule in a1-dimensionalMMS with discrete costs can be computed in deterministicLogSpace.

(23)

Finite-time horizon problem in 1-dimension

LetM+={m∈M |R(m)>0}, M={m∈M |R(m)<0}, M0={m∈M |R(m) = 0}.

Aleapis a subsequence(mk, tk),(mk+1, tk+1)in a schedule such that mk ∈M+,mk+1∈M, andR(mk)tk=−R(mk+1)tk+1=Vmax−Vmin. A leap is oftype(i, j)∈M+×M iffmk =i, mk+1=j.

Vmax

Vmin

tmax

t=0 1

2

3

4

5 6

7 8

9

(24)

Structure of an optimal schedule

Any schedule longer than 2 can be partitioned into itshead, leaps, and tail sections.

– Theheadsection ends onceVminis reached.

– Theleapssection is the maximal part of the schedule after the head section consisting only of leaps of possibly different types.

– Thetailsection starts where the leaps section ends. (It may consists of further leaps.)

Vmax

Vmin

tmax

t=0 1

2

3 4

5 6

7 8

9

Theorem (Mousa, Schewe, W., 2017)

Any schedule can be transformed without increasing its cost nor compromising its safety into one where the head and tail sections follow one of the following patterns...

(25)

10 Possible Head Patterns

t=0 t=0 t=0

t=0 t=0 t=0

Vmax

Vmax

Vmin

Vmin

(a) (b) (c)

(d) (e) (f)

t=0 t=0 t=0

(g) (h) (i)

Vmax

Vmin

1 m1 2

3 m2

1

2 m1

1 2 m1

3 m2

1 2

m1

3 m2

4 m3

1 2

m1

3

m2 1

2 m1

3

m2

4 m3

1 2 m1

3 m2

4 m3

1

3 1

2 m1

4 2

m1

m2

3 m2

m3

+ the empty one!

(26)

10 Possible Tail Patterns

Vmax

Vmin

tmax

Vmax

Vmin

(a)

tmax

(d)

tmax

(e)

tmax tmax

(g) (h)

tmax tmax

(b) (c)

tmax

(f)

(i) Vmax

Vmin

tmax 1

2 m1

1

2

m1 m2 3

1

2

m1

4 3

m3

2 m2

1 m1

1 2

m1 3 m2

4

m3 1 4

2

m1

3 m2

1 2

m1 m2 3

m3

1 2

m1

3 m2

5

1 2

m1 m2 3

4 m3 m4

+ the empty one!

(27)

Rearrange Operation

Vmax

Vmin 1 2 m1

3 m2

m3 4

20 m2

30 m3

m1

(28)

Shift Operation

Vmax

Vmin

1 2

m1

3 m2

4

m3

5 m4

20

m3

30 m4 40

m1 m2

(29)

Shift-down operation

Vmin

Vmax

1

2

mi

3 mi+1

4

mi+2

5 mi+3

3’

mi+3

4’

mi+2

mi+1

(30)

Wedge Operation

V

min

V

max

1 2 m1

3

m2

4 m3

7

6 m2

5 m2

(31)

Shrink and Stretch operations

Vmin Vmax

Stretch by Shrink by

1 2

m1

3 m2

10 20 m3

30 m4

5

4

m2

t

40 50

m3

t

Stretch by Shrink by

Vmin Vmax

1

2 mi

3 mi+1

4

5

mj

6 mj+1 20

30 mi+1

40

50

mj

t t

0

(32)

Proof by Example

Vmax

Vmin

tmax

t=0

1 7

10

11 9

12 3 13

4

5 2 6

8

Vmax

Vmin

tmax

t=0

1 6

9

10 8

11 12

7 2

3

4 5

(33)

Proof by Example

Vmax

Vmin

tmax

t=0

1 6

9

10 8

11 12

7 2

3

4 5

Vmax

Vmin

tmax

t=0 1

5

8

9 7

10 11

6 2

3 4

(34)

Proof by Example

Vmax

Vmin

tmax

t=0 1

5

8

9 7

10 11

6 2

3 4

Vmax

Vmin

tmax

t=0

1 5

7

8

9 2 10

3

4 6

(35)

Proof by Example

Vmax

Vmin

tmax

t=0

1 5

7

8

9 2 10

3

4 6

Vmax

Vmin

tmax

t=0

1 5

7 2

3 4

8 6

9 10

(36)

Proof by Example

Vmax

Vmin

tmax

t=0

1 5

7 2

3 4

8 6

9 10

Vmax

Vmin

tmax

t=0 1

7 2

8

9 10

3 4

5 6

(37)

Proof by Example

Vmax

Vmin

tmax

t=0 1

7 2

8

9 10

3 4

5 6

Vmax

Vmin

tmax

t=0 1

2

9 10

3

4

5

6 7

8

(38)

Proof by Example

Vmax

Vmin

tmax

t=0 1

2

9 10

3

4

5

6 7

8

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9 10

(39)

Proof by Example

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9 10

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9

(40)

Proof by Example

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9

(41)

Proof by Example

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9

(42)

Proof by Example

Vmax

Vmin

tmax

t=0 1

2

3

4

5

6 7

8 9

Vmax

Vmin

tmax

t=0 1

2

3

4

5 8

7 9 6

(43)

Proof by Example

Vmax

Vmin

tmax

t=0 1

2

3

4

5 8

7 9 6

Vmax

Vmin

tmax

t=0 1

2

3

4

5 6

7 8

9

(44)

Structure of an optimal schedule

There are 100 different combined patterns for the head and tail sections.

However, many of these combinations can be further reduced using one of the just defined operations.

Intuition: there can be only one point of flexibilityin a given schedule.

If there are two then one of them can be removed using the shrink - stretch operation combination.

In the end, we obtain 44 different combined patterns that cannot be further reduced and their combined length is at most 5.

Corollary

Optimal schedules for 1-dimensional MMS with a finite-time horizon always exist.

(45)

Approximation algorithms

Definition

An algorithm has arelative performance ρif for all inputsxthe cost of the solution that it computes,f(x), satisfiesOP T(x)≤f(x)≤(1 +ρ)·OP T(x), whereOP T(x)is the optimal cost for the inputx.

Definition

A fully polynomial-time approximation scheme (FPTAS) is an algorithm that runs in polynomial-time in the size of the input and1/ρ.

(46)

Constant-approximation algorithm

Theorem

A 3-approximate optimal schedule can be found inO(|M|7).

Proof (sketch)

1. Consider all schedules of length less than 3 inO(|M|2).

2. Iterate over all possible combined patterns for schedules of length more than 2.

3. Note that no pattern uses more than 5 different modes for its head and tail section (so44· |M|5possibilities in total).

4. Picking among them the cheapest schedule that only uses leaps of the same type (|M|2 possibilities) gives us a 3-approximate optimal schedule.

(47)

FPTAS

Theorem

There is an FPTAS for the optimal cost with finite time horizon problem for MMS with discrete costs in 1-dimension.

Proof (sketch)

– We first call the 3-approximation algorithm and reduce the problem to a 0−1Knapsack problem instance.

– We iterate over all possible combined schedule patterns and their modes (44· |M|5possibilities).

– In each case, the FPTAS algorithm is a bit different.

(48)

For More Details

Rajeev Alur, Ashutosh Trivedi, and Dominik Wojtczak.

Optimal Scheduling for Constant-Rate Multi-Mode Systems.

InProc. of HSCC, pages 75–84. ACM, 2012.

Dominik Wojtczak.

Optimal Control for Linear-Rate Multi-mode Systems.

InProc. of FORMATS, volume 8053 of LNCS, pages 258–273. Springer, 2013.

Mahmoud A. A. Mousa, Sven Schewe, and Dominik Wojtczak.

Optimal Control for Simple Linear Hybrid Systems.

InProc. of TIME, pages 12–20. IEEE Computer Society, 2016.

Mahmoud A. A. Mousa, Sven Schewe, and Dominik Wojtczak.

Optimal Control for Multi-Mode Systems with Discrete Costs.

InProc. of FORMATS, page (to appear). Springer, 2017.

(49)

Summary

– Multi-mode systemsare an expressive subclass of hybrid automata with decidable or even tractable analysis.

– Without discrete costs:

– Polynomial-time algorithmsfor optimal cost reachability and optimal average-cost schedulability;

– Adding eitherlocal invariantsorguardslead to undecidability.

– With discrete switching costs: – an optimal schedule may not exist;

– inNExpTime(andNP-hard) for an-optimal finite-time horizon problem, or inPSpacefor its-safe-optimal version;

– the decidability of the ()-optimal infinite-time horizon problem isnot known;

– in the 1-dimensional case:

optimal schedules always exist;

NP-completefor a finite-time horizon problem, but hasFPTAS;

infinite-time horizon version is inLogSpace.

THANKS!

References

Related documents

The optimal paths and computational cost of the VISIR system are then compared to those of the gov- erning differential equations for time-optimal path planning in dynamic

Homogenization and error analysis of an optimal interior control problem in the framework of Stokes’ system, on a domain with rapidly oscillating boundary, are the subject matters

• RL based approaches frame controller optimization problem as finding optimal control policy for the environment modeled as a Markov decision process (MDP).. This assumption

develop suboptimal solutions for the nonlinear control problem.In chapter 4, however, an optimal solution is presented for linear stochastic systems involving process time

Solving optimal unit commitment problem by considering stochastic load, random unit outages, transmission power flow limits, network bus voltages, multi area operation for

In the second section consisting of one chapter,a'total system cost'model is developed for a two—level repair—inventory system, using which, optimal inventory policies are

The general problem is to find the optimal rate (the number of bits to transmit) and transmission times for each node, which maximize network lifetime.. Both the rate and time

From a discrete polymatroid, a corresponding generalized index coding problem is constructed and it is shown that a representation to the discrete polymatroid exists if an