Better resampling strategie

[TheCodez]

Use Systematic Resampling instead of Multinomial.
Parallel implementation: https://ieeexplore.ieee.org/document/8694030

[ShepelIlya]

Hello, thanks for great job here. I want to implement systematic resampling and found repo from author of paper. But I'm new to CUDA programming and this code looks too complicated. Do you have any idea whether this code can be simplified during implementation?
At the moment I am trying to copy/paste and debug this resampling to DOGM, so if I succeed, I will create a pull request.

[TheCodez]

I would love to have systematic resampling in this repo. The code from the repo you linked is highly optimizied and thus kinda hard to understand. Your best bet is probably to stick to a simpler less optimized version like the pseudocode from the paper.

Reconstructing the pseudocode from the repo you would have something like this:

Increment cuda kernel:

...
while ( mask && tid < ( num_particles - l ) ) {
    mask = prefix_sum[tid + l] < draw;
    if ( mask ) {
        idx++;
    }
    l++;
}

Decrement cuda kernel:

...
while ( !mask ) {
    if ( tid > l ) {
        mask = prefix_sum[tid - ( l + 1 )] < draw;
    } else {
        mask = true;
    }
    if ( !mask ) {
        idx--;
    }
    l++;
}

Hope that helps a bit.

EDIT: A naive CUDA implementation can be found in the Appendix A.2 of Nicely19.

[ShepelIlya]

Ok i'll try something simple, and if it works i'll post it here.

[ShepelIlya]

Upd: I'll successfully implement parallel systematic resampling (just copy original code with little fixes).

1. It is working at rate 10 Hz if code is highly optimized as in original repo.
2. Multinomial sampling is much better for this algorithm, because every particle is resampled from 0 to num_particles time, when for systematic resampling bounds are floor[num_particles * weight_i] and floor[num_particles * weight + 1]. On my data (occupancy builded from lidar) systematic resampling works dramatically worse, because there are many particles from static objects that still resampled again and again.

So, imho for this algo multinomial sampling is the best choice.

[TheCodez]

@ShepelIlya I see. Thank you for testing this out. Would you mind sharing the code?

[ShepelIlya]

I have a several bug fixes (a little memory leak, coordinates manipulation, measurement and grid cells with SoA syntax and branch for resampling). Can I only publish all this stuff on my fork and leave merge stuff to you? If so, then I can do it in a couple of days.

[TheCodez]

Sure, sounds good.