Consider the following system:
dx/dt=f(t,x(t),u) in [t0,t1], where x(t0) is from X0, u is from U.
The value for u is set at t0 and does not change in time. I would like to find the reachable set of the system X[t]. Most textbooks and articles I have seen so far assume that u might change in time, even though sometimes the authors do not say so explicitly and call u a parameter vector. Of course, the system can be reduced to a standard ODE by considering u a state vector with the dynamics given by du/dt=0. But such an approach will increase the dimensionality of the problem, which is already the bottle neck of reachable set calculations. I wonder if there is a more elegant approach to such problems.
Update 1. For simplicity we can assume that X0 is just a single starting point. So I am interested in some description of reachable sets comprised by trajectories with different u.
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
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
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics