Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reachability using Taylor model flowpipes for nonlinear ODEs #82

Open
mforets opened this issue Apr 1, 2018 · 12 comments
Open

Reachability using Taylor model flowpipes for nonlinear ODEs #82

mforets opened this issue Apr 1, 2018 · 12 comments
Assignees
Labels
algorithm documentation Improvements or additions to documentation

Comments

@roccaa
Copy link

roccaa commented Apr 3, 2018

The thesis of Chen! You should also put the link to Flow* code which implements this thesis.

@schillic
Copy link
Member

Taylor models were recently implemented in CORA with a detailed description in this ARCH18 paper.

@mforets
Copy link
Member Author

mforets commented Nov 10, 2018

Thanks for the link. In Julia, Taylor models are implemented in JuliaIntervals/TaylorModels.jl and there's the related package JuliaDiff/TaylorSeries.jl.

@lbenet
Copy link
Collaborator

lbenet commented Jan 31, 2019

These are some further interesting links

I highly recommend Joldes' thesis.

@mforets
Copy link
Member Author

mforets commented Mar 21, 2019

In JuliaReach/Reachability.jl#537 we added the TMJets continuous post. The flowpipe is represented as a collection of hyperrectangles, and the algorithm is defined in validated_integ, at the moment in the validatedODEs branch. Thanks @lbenet 🌮 🌮 🎉 !

Eventually, it may be more convenient to just write the reachability algorithm in this repo (for extensions, eg. to do flowpipe-invariant intersections in the loop).

Examples of use are in this notebook

Screen Shot 2019-03-21 at 11 29 58


I think that we can close this issue, but before i would like to store the research literature links somewhere visible, maybe in the Reachability docs.

@lbenet
Copy link
Collaborator

lbenet commented Apr 1, 2019

Sorry for the late comment on this... Can you comment about the time for each computation?

@mforets
Copy link
Member Author

mforets commented Apr 1, 2019

If the modes are of the form x'(t) = Ax(t) + u(t), i would expect linear continuous posts to be more efficient than nonlinear ones for the same accuracy, since the linear structure can be exploited, particularly for high-dimensional systems. But the bouncing ball is "middle-ground" for different approaches, since it is only two-dimensional.

If you check again the BenchsHybrid notebook you'll see updated plots and times. At the moment the three algorithms are in the same order ~0.5-1.0sec for a time horizon of 12sec, which gives 3 jumps. Note also that some time is spent on the discrete post, which is the same function for all three. Another benchmark would be to compare the behavior without jumps.


Incidentally for the bouncing ball model with @taylorize i had to write

@taylorize function bball!(t, x, dx)
    dx[1] = x[2]
    dx[2] = -1.0 + 0.0001*x[1] # here 0.0 * x[1] doesn't work, see below
    return dx
end

i cannot pass dx[1] = -1.0 + 0.0 * x[1], dx[2] = -one(x[1]) or dx[2] = -1.0 + zero(x[1]) because this gives a δt in validated_step! that is too large (the whole time horizon T) such that solve only returns one set. I checked that validated_integ returns a single set. @lbenet Should i open an issue? In which package?

@mforets
Copy link
Member Author

mforets commented Apr 1, 2019

Another benchmark would be to compare the behavior without jumps.

OTOH the circle model, also 2D, see BenchsNLN notebook, takes ~10ms for BFFPSV and ~600ms for TMJets. It would be interesting to profile the bouncing ball to see how the time distribute between discretizaiton, continuous post and discrete post.

@lbenet
Copy link
Collaborator

lbenet commented Apr 1, 2019

Should i open an issue? In which package?

Please do so. I think it should be opened in TaylorIntegration.jl since @taylorize lives there.

@lbenet
Copy link
Collaborator

lbenet commented Apr 11, 2019

i cannot pass dx[1] = -1.0 + 0.0 * x[1], dx[2] = -one(x[1]) or dx[2] = -1.0 + zero(x[1]) because this gives a δt in validated_step! that is too large (the whole time horizon T) such that solve only returns one set. I checked that validated_integ returns a single set.

I've checking what is happening here. I think the following explains the issue: The equations of motion correspond to constant acceleration, so they are solved (exactly!) with a polynomial of degree 2 in t. If you use orderT larger than 3 you will see the problem. The problem arises because the time step is determined by the last two coefficients of the local solution, which for orderT larger than 3 are both identically zero; TaylorIntegration.stepsize! will then return a stepsize which is Inf, which is then reduced to tmax (time horizon) by TaylorIntegration.taylorstep!. In other words, the polynomial of order 2 in t is the exact solution, for all t!

We haven't come with a way to automatically consider previous coefficients, but I am thinking about this now.

@mforets Could you check that things behave "properly" if you set orderT=2 or orderT=3? Could you also open an issue at TaylorIntegration/jl ?

@mforets
Copy link
Member Author

mforets commented Apr 11, 2019

Thanks for having a close look into it. Actually with orderT equal to 2 or 3 it doesn't work: validated_integ returns a list of sets but they are all practically the same as the initial set. Also tried varying orderQ and abs_tol.

Could you also open an issue at TaylorIntegration/jl ?

See PerezHz/TaylorIntegration.jl#66

@lbenet
Copy link
Collaborator

lbenet commented Apr 11, 2019

I'll check it in more detail...

@mforets mforets transferred this issue from JuliaReach/Reachability.jl Apr 2, 2020
@mforets mforets added the documentation Improvements or additions to documentation label May 1, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
algorithm documentation Improvements or additions to documentation
Projects
None yet
Development

No branches or pull requests

4 participants