I'm looking to start a project that incorporates some form of state estimation and path planning for a simple simulated robot dynamic model, in an environment that contains obstacles. I'm hoping to use the combination of state estimation and path planning to allow the robot to efficiently navigate through its environment from an arbitrary starting position A, to another arbitrary ending position B, but was unsure where to start. With regards to the state estimation, I thought it would be good to implement a variant of SLAM (possibly Fast SLAM if it isn't too complicated), but I'm quite lost about where to start when it comes to the path planning side of the project, since there seem to be many different ways to do it. The first algorithms that seem to pop up are variants of A* and RRT*, but I was wondering if there are any "state-of-the-art" algorithms that may allow for real-time path planning. My previous work has looked at the use of convex optimization for optimal guidance and control of various dynamic systems, but it seems that using convex optimization would be very difficult in a highly constrained environment (i.e. environment with lots of obstacles). Any help would be much appreciated.
1 Answer
I am assuming that by real time path planning, you mean starting off in a partially known environment and updating your 'plan' as you gain more knowledge through your SLAM algorithm. For a real world scenario, two of the biggest concerns here would be a) taking into account new information from the sensors to update your obstacle map and plan, b) being computationally efficient to actually compute plans quickly during navigation.
Real time sampling based path planning has been examined in some recent papers: for state of the art algorithms, you can possibly look into Real Time RRT* (RT-RRT*) or RRTx, that does real time replanning as the environment information changes.
There are various other perspectives of looking at this as well. On the most basic end of the spectrum, if you're only concerned about, say, dynamically moving obstacles, the simplest algorithm to implement that can deal with planning in that scenario would be the D* algorithm or its anytime variants. On the more advanced side, you can look into the idea of SLAP: simultaneous localization and planning, that attempts to capture factors such as uncertainty and rewiring path plans as SLAM builds your environment and constructs the robot's belief.
