Reuse capt tree across control cycles (incremental updates)

[PetropoulakisPanagiotis]

Hi, first of all great work on VAMP — it is running very fast on our robot, and we are now using it successfully in real time 👍

We had a question regarding the capt tree lifecycle.

At the moment, the capt tree is created and initialized at every control cycle. From a control-loop perspective, this is quite expensive, especially when the incoming point cloud changes only slightly between cycles.

We were wondering:

Is there currently a way (or a planned approach) to initialize the tree once and then update it incrementally at each control cycle with the new incoming points?

This could significantly reduce computation while preserving behavior in slowly varying environments.

Thanks again for the great work!

[claytonwramsey]

Thanks for reaching out!

TL;DR: no :(.
The problem is that CAPTs get most of their speed advantages from punting a lot of their computation to construction time: we need all the points at once so that the search tree is perfectly balanced and that affordance sets are sufficiently tight.

I have a few ideas for making this process faster, such as skipping the test sequence construction, which might give a constant-factor improvement, but for now it is not on my current near-future plans to build this out. If I find some time later in my Ph.D. I will likely return to CAPTs and play around with a lot of these issues (construction performance? mutability? GPU acceleration? occlusion support? precision estimation?) but I'm not thinking about it right now.

If you need faster construction times, we found that we generally get good results from increasing the aggressiveness of the point cloud filtering step. Do you have hard timing estimates for how long each step (filter -> construction -> planning -> simplification) is taking? If I know that I might be able to help out as well.

[claytonwramsey]

And one more thing: if you are OK with having slow planning times (but fast construction times), you might want to use a $k$-d tree instead. It will have very poor query efficiency, to the tune of a 20-100x slowdown, but maybe that won't matter for your use case. We benchmarked against nigh when we originally wrote the CAPT paper and found that it was quite fast.