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

Downsampling is slow #2961

Open
pleroy opened this issue Apr 24, 2021 · 7 comments
Open

Downsampling is slow #2961

pleroy opened this issue Apr 24, 2021 · 7 comments
Assignees

Comments

@pleroy
Copy link
Member

pleroy commented Apr 24, 2021

There has to be a better way to approximate a trajectory by a low-degree polynomial. The current implementation does O(N Ln N) evaluations of the cubic sequentially.

@rnlahaye
Copy link
Contributor

rnlahaye commented May 3, 2021

I can see two approaches:

  1. The error in a cubic approximation can be bounded using the fourth derivative of the underlying function. Using this bound, a semi-optimal cubic spline can be constructed in O(N) time. Of course this bound is not exact and the constructed spline might not be optimal.
  2. If you are willing to restrict the segments of the spline to powers of 2 (i.e. the endpoints would be of the form (k*2^i, (k + 1)*2^i)), an optimal spline can be constructed in O(N log log N) time.

I'd be happy to send a PR for either of them.

@rnlahaye
Copy link
Contributor

rnlahaye commented May 3, 2021

Note for the first approach that there is a nice bound for cubic Hermite splines in particular; see Lemma 1 from this paper by Carlson and Hall.

@pleroy
Copy link
Member Author

pleroy commented May 3, 2021

Note that I am not at all sure that a cubic is really what we want, it was just convenient when this code was implemented. Once you have specified continuity of the position and velocity at the endpoints, a cubic doesn't give you many degrees of freedom (understatement!). A higher degree polynomial, like we use for continuous trajectory, might be preferable.

If we look at the problem as trying to find a point in a suitable function space that is "close enough" to the trajectory, I have a hunch that we could be sublinear as long as we are not looking for the closest possible match. Pick a subset of the points, find an approximation, add more points, repeat until the approximation stabilizes.

@rnlahaye
Copy link
Contributor

rnlahaye commented May 3, 2021

Since vessels are user controllable, their trajectories can have weird kinks in them. I don’t see any way to detect these without checking every point (although of course these checks do not have to be performed at interpolation time; they can be performed when the points are initially added to the trajectory).

That is, I don’t think it is possible to do better than O(N) amortized.

@eggrobin
Copy link
Member

eggrobin commented May 3, 2021

although of course these checks do not have to be performed at interpolation time; they can be performed when the points are initially added to the trajectory

This ties into our ideas in #2400 (comment) (the sections of trajectory that do not contain burns should not be serialized, and thus the burns need to be flagged in some fashion).

It would probably be a good idea to have a more concrete plan on that side before we start changing the representation from an interpolating spline to something else (downsampling and reanimation will have to coëxist, the former to make sizes mangeable in memory, and the latter to keep saves small).

Sorry, something went wrong.

@pleroy
Copy link
Member Author

pleroy commented May 4, 2021

Going forward it will be important to separate burns from coasts, both for serialization and for downsampling. I have some ideas about serialization, but I won't start coding until the stuff in Grassmannian is finalized.

Regarding downsampling: The burns are integrated using an adaptive step integrator, it's not even clear that downsampling buys us a lot, as the integrator adapts to the kinks. Surely errors of 10 m are excessive, e.g., when doing a rendezvous. The coasts on the other hand must be close to arcs of conics, so I am hoping to reuse some of the work that didn't quite pan out for #2400.

Sorry, something went wrong.

@pleroy
Copy link
Member Author

pleroy commented May 4, 2021

Possible low-hanging fruit: I ran into this code which seems rather dumb:

template<typename Frame>
Position<Frame> DiscreteTrajectory<Frame>::EvaluatePosition(
Instant const& time) const {
return GetInterpolation(time).Evaluate(time);
}
template<typename Frame>
Velocity<Frame> DiscreteTrajectory<Frame>::EvaluateVelocity(
Instant const& time) const {;
return GetInterpolation(time).EvaluateDerivative(time);
}
template<typename Frame>
DegreesOfFreedom<Frame> DiscreteTrajectory<Frame>::EvaluateDegreesOfFreedom(
Instant const& time) const {
auto const interpolation = GetInterpolation(time);
return {interpolation.Evaluate(time), interpolation.EvaluateDerivative(time)};
}

In the very common case where these functions are called with an actual point of the trajectory, maybe they could avoid constructing an interpolation and just do a lookup in the map instead.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants