Sampling based Motion Planning
If there's too much work to do and too little time, it is always a good idea to do some samples of work here and there. If a house cannot be cleaned in totality, clean a few top spots; in a new city, it is good enough to visit top touristy places; in a class it is good enough to make friends with a variety of people who'll be with you in different serious and embarrassing situations; searching for a lost million dollar cheque, it is enough to search prominent places where you'd have missed it, etc. These selected few bits of work are called as samples, and if you select the best samples, there's no need to complete the entire work given. This reduces the work significantly, but puts a more difficult work on identification of best samples to solve the problem. A few hard-working may do it all, a few crazy may leave it all, and then there are the wise who know the right thing for the right job.
So if a path needs to be searched from a source to a goal and there are infinite paths possible, there is no need to search the entire space. Instead, just search for a sampled sub-space, which happens by saying these random points seem awesome for the problem. Try navigating between neighboring samples, and if you can without collision, there's a small valid path segment as a reward. If path segments are fairly large in numbers, you get a roadmap (specifically Probabilistic Roadmap), which is the secret key to move anywhere in space to anywhere else. Let us focus, literally, between a given source and goal, select samples and search with the same into the mind. Restricting the path segments to be a tree growing from source (or goal or both source and goal), gives a Rapidly-exploring Random Tree that grows like a wild tree in search of the goal in life.
The research in sampling based motion planning is to sit in the control room of crime control and to say these areas look great for work, and these do not. Anything better than random gives you enough bragging rights. Top strategies including focusing near obstacles and especially narrow corridors known for some insane stuff. There's more than selecting samples, which is to, literally, connect the dots. You could strategize to waste a lifetime connecting two dots that seem related and important, or just be lazy and connect the obvious ones only. There are pros and cons, like the road to success was just round the corner and you were busy looking straight, or there was no shortcut to success and you kept looking for it. Inability to connect two regions can lead to no path being found for the motion planning problem. Spending too little time may not find simple ways, while spending too much time connecting spaces separated by a big obstacle in between is wasteful.
Before delving into research, it is good to know who the superstar of this domain is, or the ideal solution. The superstar depends on what you want. Let us take the simplest problem, to be able to navigate around, meaning it should be possible get a reasonably good solution irrespective of the chosen source and goal. So there should be a roadmap that has roads around all obstacles. This should be a clear bias in the design of the strategies to select the vertices and edges of the roadmap, wherein few samples far away from obstacles and edges that connect otherwise hard to connect samples are extremely precious.
The research here applies some crazy ideas to get a way around. This includes getting samples which are in the center-stage and thus can be easily seen by all samples around and are easy to connect. The higher is the visibility of samples, the easier is to connect them, the lesser are the number of samples required to make the roadmap. Even crazy is to make a roadmap inside the obstacles. No robot travels that obviously. However, it is hard to get a sample inside a narrow corridor. In computing, a gangster in the hiding by travelling through narrow lanes and corridors can be caught by surrounding him/her from all sides of the adjoining obstacles. This gives enough samples inside the corridor to connect all dots.
And the research here also takes you on a tour around the barren narrow lanes with enough corners for an adventure. The focus is to select such interesting areas and to travel them to connect places that are otherwise seen as a disconnected world altogether. This combines with the work put by peers to find and report interesting places with standard toolkit already applied. The adventure begins right there.
If you're confused of having too many strategies already, there's a simple way out, which is to use all of them. All think-tank and strategists sit and perform together. At any point of time, the ones who seem to be doing a fair deal of job are promoted and over-utilized, while the ones who are making others time a mess are terminated. There's a cruel world out here. The sampling and edge connection strategies are made hybrid and adaptive to automatically select the best ones.
Related Publications
- R. Kala (2019) On sampling inside obstacles for boosted sampling of narrow corridors, Computational Intelligence 35(2): 430-447.
- R. Kala (2016) Homotopic Roadmap Generation for Robot Motion Planning, Journal of Intelligent and Robotic Systems, 82(3): 555–575. (Download Paper)
- R. Kala (2016) Homotopy conscious roadmap construction by fast sampling of narrow corridors, Applied Intelligence, 45(4): 1089-1102. (Download Paper)
- A. Kannan, P. Gupta, R. Tiwari, S. Prasad, A. Khatri and R. Kala (2016) Robot Motion Planning using Adaptive Hybrid Sampling in Probabilistic Roadmaps. Electronics 5(2), 16. (Download Paper)
- R. Kala (2018) Increased Visibility Sampling for Probabilistic Roadmaps, In Proceedings of the IEEE Conference on Simulation, Modelling and Programming for Autonomous Robots, Brisbane, Australia, pp. 87-92. (Download Paper) (Download PPT)
