Reachability Games with Relaxed Energy Constraints
Ritam Raha
joint work with
Nicolas Markey Loïc Hélouët
INRIA Rennes INRIA Rennes
1
Games on Graphs: Qualitative/Quantitative
- Two players on a graph: typically system ($P_1$) and environment ($P_2$)
- Qualitative objectives: Reachability, Safety, Büchi
- Quantitative objectives: Energy, Mean-payoff, Discounted
2
Energy with Reachability
- Weights are intergers; w.l.o.g we start with $0$.
Objective: $P_1$ has to reach T maintaining energy level within some given bounds
3
Different Settings: Strong vs Weak Bounds
4
Strong Lower Bound Games
$P_1$ maintains energy level $\geq L$ & reach $T$
Classical Setting: Infinite path setting without reachability
- 1-player L-infinite games are in P and 2-player are in NP $\cap$ coNP
- Idea:
- $P_1$ finds a non-negative cycle and repeat
- memoryless strategies for both players
5
Reductions
With reachability: Same complexity
6
Strong Dual Bound Games
$P_1$ maintains $L \leq$ energy level $\leq U$ & reach $T$
- One player game: PSPACE-complete (reduction from Reachability of bounded one counter automaton )
- Two player game: EXPTIME-complete (reduction from Countdown Games )
With strong bounds, reachability and infinite Games are interreducible!
7
Weak Dual Bound Games
Relax one of the bounds, say the upper bound
- $P_1$ has to maintain energy level $\geq L$ & reach $T$
but
the upper bound $W$ ($U$) is weak,
i.e.,
if energy hits $\geq W$, it stays at $W$.
8
Motivation towards Weak Bounds
Can be formulated as a two player finite state game. [Hélouët et al.'18]
- An intruder takes a large number of normal actions and then does somethings bad. ✕
- With weak upper bound, this is not possible. ✔
8
Infinite vs Reachability in Weak Dual Bound Games
9
Memory for $P_2$
10
1 Player Game
- Consider a winning strategy $\sigma$ of $P_1$.
- Any outcome of $\sigma$ will not have any zero cycle or negative cycle.
- Now, $P_1$ has two options:
- win in an acyclic path
- choose a positive cycle; iterate enough to increase energy; continue
11
Technical Observations
- Same cycle can be positive or negative cycle depending on the initial energy level.
$W = 4$.
- $x=4 \Rightarrow$ a negative cycle
- $x=1 \Rightarrow$ a positive cycle
- A feasible positive cycle can be iterated and the output energy stabilizes.
Why?
12
Positive Cycle
- Reach $s_1$ with energy $\geq 5 (L+a)$ and reach energy level $14 [W-m]$
- #Iterations can be bounded by W-L.
13
Winning Path
14
Universal Cycle
Universal cycle on $q$: a cycle that can be taken with initial energy $L$.
15
NP algorithm for 1 Player Game
- For every cycle, there is a universal cycle.
- Winning paths: $\beta_1 \cdot {\tau_1}^{W-L} \cdot\beta_2\cdot{\tau_2}^{W-L} \cdots \beta_k \cdot {\tau_k}^{W-L}$ where, $\tau_j$'s are universal.
- Use optimal universal cycles: $k<|Q| \Rightarrow$ NP Algorithm!!
- Cycles(EXPTIME) $\Rightarrow$ Universal Cycles(EXPTIME) $\Rightarrow$ Optimal UC(NP) $\Rightarrow$ P ?
- Idea for P:
- Find Optimal UC in P
- Find the winning path in P
16
Road to P: DAG-construction
17
Polynomial Algorithm
- Compute $m_q$ for each state q if it has an optimal universal cycle
- Construct $G'$ adding transition $\upsilon_q: q \xrightarrow{:=W-m_q} q$.
- Winning paths: $\beta_1 \cdot \upsilon_1 \cdots \beta_k\cdot \upsilon_k$
- path size $ \leq (|Q+1|)^2$:
PTIME!
Corollary: Two player LW-reachability is in coNP.
18
Conclusion
- With strong bounds, reachability does not differ from the classical energy objective settings.
- Relaxation of a bound does change the strategies for $P_1$, but it is still in coNP.
19
