search

ros-navigation / navigation2

ROS 2 Navigation Framework and System
https://nav2.org/
Other
2.64k stars 1.31k forks source link

AMCL is not "Adaptive" #1152

Closed yathartha3 closed 5 years ago

yathartha3 commented 5 years ago

Localization will benefit from using an adaptive sample set size. The algorithm that is currently implemented is the "Augmented Monte Carlo Localization".

Why this matters: Adaptively changing the number of sample allows for computational efficiency. Example, when you start up the robot, you might need 10000 particles. However, once it has localized, it probably needs less particles to localize. The algorithm is in page 264 of Probabilistic Robotics book, and is named KLD_Sampling_MCL.

For some reason the legacy AMCL code has this commented out saying

// Can't (easily) combine low-variance sampler with KLD adaptive // sampling, so we'll take the more traditional route.

So at this point, the A in AMCL implementation stands for augmented, and not adaptive (which was surprising to me).

yathartha3 commented 5 years ago

I can implement the adaptive version. However, I wanted someone to take a look to confirm this issue, and how we might implement the adaptive version. OR, What is a replacement for AMCL?

SteveMacenski commented 5 years ago

I would definitely not disagree that there are benefits from being derived from actually doing this sampling, but before starting that since it should be relatively straight forward, I would try to create a set of metrics and environments to make sure that those changes reflect substantive improvements across many use-cases since this is a (very) package alot of people rely on with their current set of parameters. Metrics like improved localization / response, amount of additional computation time, which then would affect the maximum number of particles a particular microprocessor could have at peak, etc

I almost wonder if you're motivated and there's a business case if it might be better to just redo AMCL entirely based on modern tools. Someone in C++land must have a heavily used pf implementation, same with the math and random sampling from a distribution. Add in the plugin based motion models for omni/diff/ackermann and that's off to the races.

SteveMacenski commented 5 years ago

Repeating back to you: That comment also indicate that someone tried to do KDL sampling but the variance in particles were consistently low enough that something wasn't either working right or worth the complexity. I dont know if that gives you a clue as to why it was removed, but I'd have to pull out a notebook and my copy of Dieter's book to figure it out

I can't say there's much love for AMCL, and I've heard @gerkey (amongst others including myself) say on several occasions we should just let it die. For various reasons including that, I'm of the opinion that AMCL should remain until we all agree upon something better, but the bandwidth on improving it would probably be better spent looking for better alternatives

yathartha3 commented 5 years ago

I would definitely not disagree that there are benefits from being derived from actually doing this sampling, but before starting that since it should be relatively straight forward, I would try to create a set of metrics and environments to make sure that those changes reflect substantive improvements across many use-cases since this is a (very) package alot of people rely on with their current set of parameters. Metrics like improved localization / response, amount of additional computation time, which then would affect the maximum number of particles a particular microprocessor could have at peak, etc

Since many people have their current set of params, the 'augmented' can be the default. With the adaptive version, there won't be introduction of new params, since there are already all the necessary params, but are not being used. But how it will affect other things, is something I don't know.

I almost wonder if you're motivated and there's a business case if it might be better to just redo AMCL entirely based on modern tools. Someone in C++land must have a heavily used pf implementation, same with the math and random sampling from a distribution. Add in the plugin based motion models for omni/diff/ackermann and that's off to the races.

Plugins for different motion models is a really good idea.

I am not saying AMCL has to be made adaptive, but rather just pointing it out since I was surprised it was not already doing it.

yathartha3 commented 5 years ago

Might be useful when we are testing on bigger maps, or with compute limited computers. However, users can always try to tune the number of particles using params. Will close for now. Reopen if needed.