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

Add caching lazy MinkowskiSum #342

Closed
schillic opened this issue May 17, 2018 · 1 comment
Closed

Add caching lazy MinkowskiSum #342

schillic opened this issue May 17, 2018 · 1 comment
Assignees
Labels
feature ➕ A new feature performance 🐎 More efficient code

Comments

@schillic
Copy link
Member

schillic commented May 17, 2018

In Reachability.jl we can build lazy sums in a loop. In each loop iteration we query the support vector of the sum and add one more element. It would be more efficient if the sum stored the support vector result for most summands and only computed the support vector of the remaining set(s).

Example:

sum = CSum([X1, X2, X3])
σ(d, sum)
# in the background, `sum` computes `r1 = σ(d, X1) + σ(d, X2) + σ(d, X3)`
# and stores ``[X1, X2, X3] => [(d, r1)]`
sum = sum + X4
# in the background, `sum` stores `[X1, X2, X3] => [(d, r1)], [X4] => []`
σ(d, sum)
# in the background, `sum` computes `r2 = r1 + σ(d, X4)`
# and stores `[X1, X2, X3, X4] => [(d, r2)]`

It could be helpful to have #269 first.

@schillic schillic added feature ➕ A new feature performance 🐎 More efficient code labels May 17, 2018
@schillic schillic self-assigned this May 22, 2018
@mforets
Copy link
Member

mforets commented May 22, 2018

👍 i think this approach can also useful for other set representations. as a design strategy, in a future revision we could use composition like:

struct CachedLazySet{N, ST<:LazySet{N}, CT} <: LazySet
    X::ST
    cache::CT
end

schillic added a commit that referenced this issue May 23, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature ➕ A new feature performance 🐎 More efficient code
Projects
None yet
Development

No branches or pull requests

2 participants