05 Aug

Motion Planning 2: Sampling-Based Methods

Yuki-shirai Motion Planning

Sampling-based motion planning approaches, such as Probabilistic RoadMap Method (PRM) and Rapidly-exploring Random Trees (RRT) , avoid the discretization problems of graph-based algorithms by randomly sampling the continuous domain. This scales more effectively to high-dimensional problems, but makes their search probabilistic. Thus, compared with the properties of graph-based algorithms, they are probabilistically complete, having a probability of finding a solution if one exists, that goes to one as the number of samples goes to infinity. Optimal variants, such as RRT* and PRM* are also asymptotically optimal, converging asymptotically to the optimal solution with probability one as the number of samples goes to infinity. Recently, BIT* is proposed that is able to find optimal solutions with better convergence rate against RRT* reusing previous suboptimal solutions efficiently.

The main disadvantage of sapling-based algorithms is that the obtained paths often manifest redundant and jerky motion and hence require post processing to smooth and shorten the computed trajectories, which typically takes quite time to compute. Furthermore, they suffer from finding samples that satisfy many complicated constraints, especially for very high DoF robots such as humanoid robots, in cluttered environments.

Here, I illustrate each of the concepts that constitute typical sampling-based motion planning algorithms with the need to satisfy the constraints.

  • Samplers: If the environment is occupied by a number of obstacles, then it is very difficult for the samplers to find the node within the collision-free space. A planner somehow needs to find the sample configurations that satisfy constraints or guide the search towards the area where the collison-free is guaranteed.
  • Metrics and nearest neighbor data structure: Normally, you can use the L_2 norm as the metric to compute the edge cost between the current node to the sampled node. However, this is very difficult under the configuration space with constraints because the typical trajectory is line anymore and it can be curved and twisted, leading to the inconvenience of using l2 norm as the metric. You can use the Riemannian metric, but the computation would be very expensive.
  • Local planners: If you use the methods something like interpolation, this would not work anymore as you can imagine due to many constraints. In addition, normally, the curvature and structure of the space is unknown a priori so that it is very difficult for the planner to consider the constraints before the planner runs. Even for relatively simple robots such as wheeled robots, you need to consider good local planners to satisfy constraints like stearing constraints, energy constraints. I do recommend that you can use trajecotry optimization algorithms, which I will explain in my next blog.
  • Coverge estimates: To the best of my knowledge, "no" constrained sampling-based planner has constructed a planning method that use a converge estimate in its planning process. This is one of the largest open problem in sampling-based planners.

Reference:

M. Elbanhawi and M. Simic, “Sampling-Based Robot Motion Planning: A Review,” IEEE Access, vol. 2, pp. 56–77, 2014, doi: 10.1109/access.2014.2302442. 
 @article{Elbanhawi_2014, title={Sampling-Based Robot Motion Planning: A Review}, volume={2}, ISSN={2169-3536}, url={http://dx.doi.org/10.1109/ACCESS.2014.2302442}, DOI={10.1109/access.2014.2302442}, journal={IEEE Access}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Elbanhawi, Mohamed and Simic, Milan}, year={2014}, pages={56–77} }
< bib >
Z. Kingston, M. Moll, and L. E. Kavraki, “Sampling-Based Methods for Motion Planning with Constraints,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, no. 1, pp. 159–185, May 2018, doi: 10.1146/annurev-control-060117-105226. 
 @article{Kingston_2018, title={Sampling-Based Methods for Motion Planning with Constraints}, volume={1}, ISSN={2573-5144}, url={http://dx.doi.org/10.1146/annurev-control-060117-105226}, DOI={10.1146/annurev-control-060117-105226}, number={1}, journal={Annual Review of Control, Robotics, and Autonomous Systems}, publisher={Annual Reviews}, author={Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.}, year={2018}, month=may, pages={159–185} }
< bib >
J. D. Gammell, T. D. Barfoot, and S. S. Srinivasa, “Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search,” The International Journal of Robotics Research, vol. 39, no. 5, pp. 543–567, Jan. 2020, doi: 10.1177/0278364919890396. 
 @article{Gammell_2020, title={Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search}, volume={39}, ISSN={1741-3176}, url={http://dx.doi.org/10.1177/0278364919890396}, DOI={10.1177/0278364919890396}, number={5}, journal={The International Journal of Robotics Research}, publisher={SAGE Publications}, author={Gammell, Jonathan D and Barfoot, Timothy D and Srinivasa, Siddhartha S}, year={2020}, month=jan, pages={543–567} }
< bib >

Next Post Previous Post

Search

Popular Tags

foray origami robots blimp ducky vr edg SLAM computer vision computational design roco slam Origami rocolib arduino RoCo design Robot Compiler simulation Motion Planning autonomy edg-model mesh reinforcement learning; multi-agent; mean-field; logics create; kalman filter; motors imu friction mesh network tank esp32 networking contacts multi-agent pushing auxetic machine learning dynamics esp now visual processing wireless control communication webapp pcbs structure ROCO i2c path planning cars Robotica reinforcement learning computer skill openmv test motor dataset visual DARPA odometry Battery surface structure power consumption dash port-arrays modeling origami paper frequency diversity semantic infrastructure auxetics feedback gondola machine vision Consensus bistable auxetic controller gestural intuition mixed reality unit cell robot crawler gestural interface open house network create; kalman filter; EM; refactoring 4-wheeled darpa; create; icra2021 apriltags lidar logic control FORAY perception Quantum Information crazyflie 433mhz optimization propeller Foray structures sensors environmental design radio DER Kullback-Leibler Divergence lasercutter tutorial von Mises Fisher Distribution IR simulink legs project management localization distributed optimization blynk Auxetics painlessmesh experiment results offline reinforcement learning exam research proposal altimeter thrust PCB sensor fusion gate or webots multi-agent path planning UAV RL integration test arnhold joystick balloon test vision processing pushing problem modeling contacts mesh networking motor configuration nodemcu swarm object detection fusionbot ros2 rviz2 gazebo conference matlab arduino nano decentralized surfaces keyboard IROS Integrated Demo throughput peripheral device paper review reinforcement learning; motorized boats Writing slam; paper review rhino Short Post range distance surp origami robot nylon pvdf elastic polymers plastic hot plates reinforcement learning; multi-agent; mean-field; game theory; mean field; reinforcement learning current reinforcement learning; multi-agent; Xbee Zigbee robot compiler spi contact neural network dynamic modeling quasi-static modeling edg-examples Kalman Filter port-array von Mises Fisher von Mises-Fisher literature review multipack car Zero Elastic Energy modes swarm control solar cars system ID serial monitor edg-ide Discrete Elastic Rods ceres debug Consensus Algorithms coriolis force dynamic model proposal wtf deep learning pdms interpolation wireless signal strength reinforcement learning; multi-agent; decentralized misc reinforcement learning; multi-agent; mean-field; stationary demo video flytrap papers steering structured field pivoting differential power detectionrate color shape edg-refactoring pain python vision Machine Learning Q-Learning Model-Free release conferences quasi-static pushing liquid crystal elastomer nonholonomic systems iot grant feedback-controlled controls trajectory optimization surface contact Characterization tool ML multi-agent path finding Liquid Crystal Elastomers Learning kinematic_model reservoir computing 2.4 GHz concept 433 MHz Bayesian Network creative Computer skill internal silicone integrated system instance segmentation marginal cost pricing bootstrapping Bayesian networks ensemble methods offline Rl hardware manipulation COVID 19 paper cutter ESP32 kalman filter; multi-robot state space delta tolling buoyancy chiral square unit cell pressure distribution model prediction thrust configuration grid fabrication firmware protobuf #activecapturingmechanism #claw 3D-CHESS; kalman filter boxboat tracking model-based RL von Mises Distribution slam; flowchart; spring-mass 3D-CHESS; 433 rssi signal strength multirobot system writing in-situ design buoyancy equations boat deployment cell cameras der newton's method Barycenter Euler-Bernoulli beam sma-based actuator game theory Bessel functions von Mises-Fisher Distributions ide HDL board design battery current sensor ZMP center of friction Multi-Agent Systems code balloon semantic segmentation MIMO communications ICRA ICML guassian processes probabilistic neural networks graph generators MBRL batch learning ros edg-compiler multirobot optitrack adaptive control motor driver submission DNN kalman filtering point cloud 2.4ghz latency scenic codesign presentations machine training preliminary exam multiple devices inkscape material multi-object tracking ICLR Python actuation catching mechanism integration flapping color_segmentation lab_data result segmentation on multiple object and centers finding competition prelab multiple blimps pid defender Synthesizable Radio 3d printing kalman filter motor distribution barometer detection lift force depth estimation cad solidworks design tool pixracer pixhawk ardupilot flight controller regression fly test sensor selection