search

ros-navigation / navigation2

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

Potential AMCL Improvements (NDT, QMCL, etc) #1391

Open SteveMacenski opened 5 years ago

SteveMacenski commented 5 years ago

We should consider how to improve on AMCL by replacing, refactoring, or reconsidering algorithms given the state of the art. NDT is another method and a paper https://www.researchgate.net/publication/261352911_Normal_distributions_transform_Monte-Carlo_localization_NDT-MCL/link/587c8d6608ae4445c067dbb4/download uses NDT-MCL for localization to increase quality greatly resembling reflector-level localization errors (really good). There's also maybe (?) an MVP version here: https://github.com/OrebroUniversity/perception_oru/tree/port-kinetic

There's also an on-going discussion here (https://github.com/VorpalBlade/quickmcl/issues/15) about potentially moving away from the software package that implements an MCL, AMCL, to another, QuickMCL (QMCL?).

Benefits are

Drawbacks

It seems like a good way to go if we can put in a little elbow grease. I'm not sure if folks' interests in getting away from AMCL are solely based on the AMCL-specific implementation or away from an MCL based localizer. I can see benefits (generic, works for most people) and drawbacks (generic, doesn't work great for anyone) of either direction. NDT is what the autonomous driving folks use, maybe a good option as another alternative algorithm.

This ticket is to bring up both QMCL as a potential alternative as well as get feedback if people think we should migrate entirely to a new default localization algorithm, and what that might be. Points to any suggestion that can be extended to 3D lidars as well as 2D (which MCLs and NDTs can be)

Adding additional restrictions on particle sampling. For instance, not allowing particles to be populated in collision states or not populating new particles that would require going through a wall.

https://discourse.ros.org/t/localization-architecture/8602/3

Take some queues from the autonomous driving crowd if we can find options computationally feasible for us

image

(using mulitiple sources like vision, laser, gnss looks interesting so we're not just using laser)

crdelsey commented 5 years ago

Hmm. So, the option's are, port QuickMCL or fix AMCL, or leave AMCL alone and get a different type of algorithm going.

I don't see MPL-2 as a significant enough improvement over LGPLv2 to warrant the switch to QuickMCL. Making the switch involves a bunch of porting work and gains some performance benefits at the expense of features, so on technical reasons there's pros and cons.

For me, I think I'd rather spend the effort on making an new Apache license 3D capable localizer if one doesn't already exist.

VorpalBlade commented 4 years ago

I would be willing to consider Apache license. I do also believe that having a 2D localiser is still useful, since a lot of robots (especially student projects) can be quite computationally limited, running on for example a raspberry pi with a simple 2D laser. 2D MCL is quite a lot computationally cheaper than for example NDT-MCL (I'm not really familiar enough with other 3D localisation approaches to comment on those).

SteveMacenski commented 4 years ago

Well its also pretty trivial to extend AMCL to 3D if you have a 3D map to work with. its the same concept with raycasting except now its with voxels instead of pixels.

Anyhow, Apache would be great just to conform with the rest of the repo. With that said, things have changed on our end (most of the Intel people are no longer working on this project) and I will not have any time in the foreseeable future to work on this. However, I would like to see this and I would work with someone to port it to ROS2 and have it included, but I will not be able to do it myself in at least the 12 month horizon.

jmtc7 commented 4 years ago

The attached file exposes several potential alternatives and compares them based on the accuracy and cycle time they claim. A convenient way to go seems to implement vanilla NDT-MCL (Normal Distribution Transforms Monte-Carlo Localization), which could be improved in the future, giving particular attention to the performance in dynamic environments.

AMCL_Alternatives_for_ROS_2_s_Navigation_Stack.pdf

SteveMacenski commented 4 years ago

Once we have a design to start implementing, append it to that doc and lets stick it in the /docs directory.

SteveMacenski commented 4 years ago

(Consider also using openMP, TBB, or GPU to speed up various elements like particle filter updates or matching or what have you)

abylikhsanov commented 3 years ago

Hi, is someone actively working on this or done something already? As I am thinking to start from Vanilla AMCL as per suggestion and adding up the rest to come up with a robust commercial localization. The only thing is that I am planning to use ROS Noetic (not ROS2).

SteveMacenski commented 3 years ago

This is in the works currently, yes. But we have no plans to ever support ROS 1(in fact, I'd probably be unreasonably opposed to porting it back to ROS 1 as its a big draw for Nav2)

abylikhsanov commented 3 years ago

Can you share where can I find the current status? As before starting, it would be unreasonable to start everything from scratch if some work has been done already. Regarding the ROS1 port, this is okay, I can do that myself as in the environment where I am working everyone still use ROS1

SteveMacenski commented 3 years ago

Its in the works, this is the specific work that's been done https://github.com/ros-planning/navigation2/pull/1930 but unfortunately there's not a concise way to explain the status. I'm not sure there's a way to really collaborate in ROS 1.

vishwaslip commented 1 year ago

Hello, is there a particular reason the progress on this was halted? I have read through some of the papers, and DT-NDT-MCL seems very promising, though has there been second thoughts about the algorithm? Have there been discussions about better alternatives?