Dear Sanjay,

Thank you for the answer. By no means I would expect the problem to be solved in this general setting. Rather, I am interested if such a problem has been addressed at all given some reasonable assumptions about the RHS such as Lipschitz continuity and convexity. At the moment I am trying to find any practical approaches to calculation of reachable sets for constant controls. To be frank, I am not even sure I have seen any results for linear systems for that matter.

Regards,

Stanislav

Fine, Stanislav.

In that case, you may wish to look into the concept of reachable domains through stable trajectories !

So study of some follow-up work on Lyapunov or Popovian stability concepts could give you some leads.

Of course, this is just a suggestion - not an assurance that those routes will immediately lead to a tangible answer !!

With best wishes.

-Sanjay

Sanjay, thank you for the tip! I will try searching there.

For nonlinear systems (even planar), it can be very difficult just to describe the reachable set analytically. It can look pretty weird (cf., e.g., Arnold's cat).

One result for a particular class of nonlinear monotone systems is reported in the attached paper. 

Article Detecting and enforcing monotonicity for hybrid control syst...

Dear Stanislav,

there are myriads of methods to approximate reachable sets of ODEs. Two examples that even over-approximate these sets are presented in the following references:

1. Feedback Refinement Relations for the Synthesis of Symbolic Controllers, (Reissig, Weber, Rungger), Section VIII, DOI 10.1109/TAC.2016.2593947

This method requires to numerically solve one initial value problem in the original ODE, giving the center of some rectangle R that overapproximates the reachable set, plus solving anover IVP in some linear ode, giving the radii of R.

2. Computing Abstractions of Nonlinear Systems (Reissig), DOI 10.1109/TAC.2011.2118950

This method requires solving several IVPs in the original ODE plus the associated adjoint equation, and yields a polyhedron that overapproximates the reachable set.

Under-approximating reachable sets is also possible.

Dear Dmitry and Gunther,

Thank you for your references. As I understand by looking them through, the problem is again set for control that changes in time, which is not my case. Do you think those methods can potentially be adapted to constant control without losing their advantages over just crude sampling over the set U and solving the resulting ODEs?

Regards,

Stanislav

Dear Stanislav,

Let's first see what kind of reachable sets you are after. There are (at least) 2 possibilities.

1. You fix x_0 and vary u (but keep it constant over [t_0,t_1]) . In this case much will depend on the convexity of the set f(t,x(t),U), where U is the set of admissible control values. If this set is convex for all t, x then you can find a good approximation for the reachable set. Look for papers on the reachability sets for differential inclusions.

2. If you take x_0 from X and fix u, then you can also find a good approximation for the reachable set (at least for small t_1-t_0). I believe this is what Gunther meant (correct me if I'm wrong). If you are lucky enough to have a good nonlinear system (e.g., a monotone one) you can describe the reachable set exactly. This is what I was referring to.

Dear Dmitry,

I am sorry, but I do not quite understand what you mean. Let us assume that x0 is fixed. I cannot take the union of f(t,x(t),u) over U because this will imply change of control in time. I mean the resulting differential inclusion must have a single-valued right-hand side except for time t=t0. But I cannot think of any nice way to describe it for other t - I will have to include the dependence on u0. But then I will be back to square one)

The second approach will work in my case if I extend the state variables to include u with the dynamics du/dt=0. But my question now is if I can avoid it. Anyway, thank you for the tip with monotone systems! Unfortunately, this is not my case but I will keep this method in mind for the future.

Regards,

Stas

Dear Muhammad,

Thank you for the answer, but right now I am searching for the results on a particular type of systems, not the general theory of reachable sets. 

Stanislav,

You are right, indeed. This won't be a differential inclusion, but rather a family of vector fields parametrized by a continuous index u. Right now I cannot recall any result on the approximation of reachable sets for such a problem, but there must be some. I'd be interested if somebody could come up with some refs.

Stanislav,

I am not aware of a method that works in your case without increasing the number of state variables by one. Whether or not this is feasible depends on your overall problem: What do you want to do with the computed reachable set(s)? What is the prescribed accuracy of approximation ? And most importantly, how many such sets do you intend to approximate?

Hi Stanislav,

I saw your question four years too late, so I guess you have moved on.

In case this still matters:

Reachable sets are not the right keyword for your question. You are looking at an ODE with a parameter, and you want to know how the solution depends on the parameter.

You will not be able to compute the set you are looking for without significant extra cost. Depending on the problem you *really* want to solve, there may be workarounds.

In case you want to discuss this further, please email me. I don't look at this platform very often.

Janosch