tulip.abstraction.discretize() produces region outside of given domain

[krooken]

tulip.abstraction.discretize() throws an exception because a generated region is outside of the given domain.

Code:

import tulip as tlp
import tulip.hybrid
import tulip.abstract
import polytope as poly
import numpy as np

# Continuous state space
cont_state_space = poly.box2poly([[0., 45.], [0., 10.]])

# System dynamics (continuous state, discrete time): simple integrator
h = 0.5
A = np.array([[1.0, h], [0., 1.0]])
B = np.array([[h**2/2.0], [h]])
E = None

# Available control, possible disturbances
U = poly.box2poly(np.array([[-5., 5.]]))
W = None

# Construct the LTI system describing the dynamics
sys_dyn = tlp.hybrid.LtiSysDyn(A, B, E, None, U, W, cont_state_space)

print(sys_dyn)


# Define atomic propositions for relevant regions of state space
cont_props = dict()
cont_props['target'] = poly.box2poly([[40., 45.], [0., 10.]])
cont_props['init'] = poly.box2poly([[0., 5.], [0., 10.]])
A = np.array([[0.0, 1.0], [1.0, 0.0], [0.0, -1.0], [-1.0, -2.0]])
b = np.array([[10.0], [22.0], [0.0], [-20.0]])
cont_props['near_cross'] = poly.Polytope(A, b)

# Compute the proposition preserving partition of the continuous state space
# noinspection PyTypeChecker
cont_partition = tlp.abstract.prop2part(cont_state_space, cont_props)
print(cont_partition)

# Abstraction takes some time
disc_dynamics = tlp.abstract.discretize(
    cont_partition, sys_dyn,
    closed_loop=False, conservative=True,
    N=1, min_cell_volume=0.01, plotit=False,
    simu_type='bi', trans_length=1
)

Error message:

Traceback (most recent call last):
  File "...\tulip-control\tulip\abstract\discretization.py", line 527, in discretize
    plot_every)
  File "...\tulip-control\tulip\abstract\discretization.py", line 947, in _discretize_bi
    prop_regions=part.prop_regions
  File "...\tulip-control\tulip\abstract\prop2partition.py", line 495, in __init__
    raise ValueError(msg)
ValueError: Partition: Region:

	 Polytope number 1:
	 Single polytope 
		  [[ 0.89443  0.44721] |    [[ 40.80824]
		   [ 0.      -1.     ] x <=  [  0.     ]
		   [-0.97014 -0.24254]]|     [-43.65641]]

		
is not subset of given domain:
	Single polytope 
  [[ 1.  0.] |    [[45.]
   [ 0.  1.] x <=  [10.]
   [-1. -0.] |     [-0.]
   [-0. -1.]]|     [-0.]]

The polytope looks like this:

[murrayrm]

That's pretty odd. You might try playing around with the parameters in discretize. In particular, setting N=1 is asking that your control get to the next polygon in the discretization in just one step, which seems like it might be a bit over constrained. (That doesn't excuse the behavior, but if you find something that works it might help us identify what is going wrong.)

@tichakorn832 Any ideas?

[krooken]

This is not directly obstructing me. I was surprised to receive this error, so I thought I should report it.

Setting N=2 or increasing the sample time of the dynamical system (h=0.7) avoids this error. Even setting N=2 and h=0.35 is fine. I've tried to simplify the problem formulation by removing propositions and decreasing the size of the domain as much as possible, but I cannot pinpoint exactly what part is causing this issue.

The result of this abstraction is later synchronized with a transition system of the environment, and then a controller is synthesized. If the constraints are relaxed I get a too coarse abstraction, and a controller does not exist. At the same time, for some parameter combinations the abstraction runs for too long to be practical, and in other combinations the subsequent synthesis causes stack overflows. So I have to find an acceptable balance :)

[krooken]

It seems like this issue is fixed if tulip-control/polytope#66 is accepted.

[murrayrm]

Thanks @krooken. I'll try to look through your PRs and approve them this weekend if nobody else (@tichakornw, @slivingston, @johnyf, @necozay) gets to them first.

[murrayrm]

Update: tulip-control/polytope#66 has conflicts that need to be resolved before we can merge.

[krooken]

Yeah, I shouldn't have added those commits as two separate PRs. I have done the rebase now.