{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:15:25Z","timestamp":1760346925603,"version":"3.41.2"},"reference-count":70,"publisher":"ASME International","issue":"1","license":[{"start":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T00:00:00Z","timestamp":1607558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.asme.org\/publications-submissions\/publishing-information\/legal-policies"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["634433","1634431"],"award-info":[{"award-number":["634433","1634431"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In many manufacturing applications, robotic manipulators need to operate in cluttered environments. Quickly finding high-quality paths is very important in applications that require high part fix and frequent setup changes. This paper presents a point-to-point path planning framework for manipulators operating in cluttered environments. It uses a bi-directional tree-search to find path and facilitates finding a balance between path quality and planning time. The framework dynamically switches between search strategies based on the search progress to produce high-quality paths quickly. This paper three main contributions. First, we extend a previously developed sampling-based modular tree-search. Specifically, we present a strategy that can sample effectively in challenging regions of the search-space by using local approximations of the configuration space. Second, we add new strategies and scheduling logic that decreases the failure rate as well as the planning time compared to the prior work. We also present an inter-tree connection strategy that adapts to collision information gathered over time. We introduce a scheduling rule that regulates the exploitation of focusing hints derived from the workspace obstacles. Third, we present theoretical reasoning behind strategy switching and how it can help decrease planning times and increase path quality. Together, these new features the reduce average failure rate by a factor of 4 and improve the average planning time by 22% over the previous work.<\/jats:p>","DOI":"10.1115\/1.4048619","type":"journal-article","created":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T00:43:31Z","timestamp":1601599411000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":12,"title":["Strategies for Speeding Up Manipulator Path Planning to Find High Quality Paths in Cluttered Environments"],"prefix":"10.1115","volume":"21","author":[{"given":"Pradeep","family":"Rajendran","sequence":"first","affiliation":[{"name":"Center for Advanced Manufacturing, University of Southern California, Los Angeles, CA 90007"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shantanu","family":"Thakar","sequence":"additional","affiliation":[{"name":"Center for Advanced Manufacturing, University of Southern California, Los Angeles, CA 90007"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prahar M.","family":"Bhatt","sequence":"additional","affiliation":[{"name":"Center for Advanced Manufacturing, University of Southern California, Los Angeles, CA 90007"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariyan M.","family":"Kabir","sequence":"additional","affiliation":[{"name":"Center for Advanced Manufacturing, University of Southern California, Los Angeles, CA 90007"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satyandra K.","family":"Gupta","sequence":"additional","affiliation":[{"name":"Center for Advanced Manufacturing, University of Southern California, Los Angeles, CA 90007"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2020,12,10]]},"reference":[{"key":"2021011101554885900_CIT0001","first-page":"1329","article-title":"Accounting for Part Pose Estimation Uncertainties During Trajectory Generation for Part Pick-up Using Mobile Manipulators","author":"Thakar","year":"2019"},{"key":"2021011101554885900_CIT0002","first-page":"981","article-title":"Towards Time-optimal Trajectory Planning for Pick-and-Transport Operation With a Mobile Manipulator","author":"Thakar","year":"2018"},{"key":"2021011101554885900_CIT0003","doi-asserted-by":"crossref","DOI":"10.1115\/MSEC2019-3027","article-title":"Towards Remote Teleoperation of a Semi-autonomous Mobile Manipulator System in Machine Tending Tasks","author":"Annem","year":"2019"},{"key":"2021011101554885900_CIT0004","doi-asserted-by":"crossref","DOI":"10.1109\/COASE.2019.8843209","article-title":"Task Assignment and Motion Planning for Bi-manual Mobile Manipulation","volume-title":"IEEE International Conference on Automation Science and Engineering (CASE)","author":"Thakar","year":"2019"},{"issue":"1","key":"2021011101554885900_CIT0005","doi-asserted-by":"crossref","first-page":"27","DOI":"10.5772\/53939","article-title":"Safe Human-robot Cooperation in An Industrial Environment","volume":"10","author":"Pedrocchi","year":"2013","journal-title":"Int. J. Adv. Rob. Syst."},{"key":"2021011101554885900_CIT0006","first-page":"101003","article-title":"Building Free-Form Thin Shell Parts Using Supportless Extrusion-Based Additive Manufacturing","volume":"32","author":"Bhatt","year":"2020","journal-title":"Addit. Manuf."},{"issue":"7","key":"2021011101554885900_CIT0007","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/MSPEC.2008.4547508","article-title":"Three Engineers, Hundreds of Robots, One Warehouse","volume":"45","author":"Guizzo","year":"2008","journal-title":"IEEE Spect."},{"key":"2021011101554885900_CIT0008","first-page":"4161","article-title":"Towards Control and Sensing for An Autonomous Mobile Robotic Assistant Navigating Assembly Lines","author":"Unhelkar","year":"2014"},{"key":"2021011101554885900_CIT0009","first-page":"278","article-title":"A Robotic Cell for Performing Sheet Lamination-Based Additive Manufacturing","volume":"27","author":"Bhatt","year":"2019","journal-title":"Addit. Manuf."},{"key":"2021011101554885900_CIT0010","doi-asserted-by":"crossref","DOI":"10.1109\/ICRA.2019.8794275","article-title":"Generation of Synchronized Configuration Space Trajectories of Multi-Robot Systems","author":"Kabir","year":"2019"},{"key":"2021011101554885900_CIT0011","doi-asserted-by":"crossref","DOI":"10.1109\/ICRA40945.2020.9196667","article-title":"Incorporating Motion Planning Feasibility Considerations During Task-agent Assignment to Perform Complex Tasks Using Mobile-manipulators","author":"Kabir","year":"2020"},{"key":"2021011101554885900_CIT0012","doi-asserted-by":"crossref","DOI":"10.1109\/ICRA.2019.8794353","article-title":"Identifying Feasible Workpiece Placement with Respect to Redundant Manipulator for Complex Manufacturing Tasks","author":"Malhan","year":"2019"},{"key":"2021011101554885900_CIT0013","first-page":"351","article-title":"A Systematic Approach for Minimizing Physical Experiments to Identify Optimal Trajectory Parameters for Robots","author":"Kabir","year":"2017"},{"issue":"2","key":"2021011101554885900_CIT0014","doi-asserted-by":"crossref","first-page":"021004","DOI":"10.1115\/1.4038954","article-title":"Handling Perception Uncertainty in Simulation-based Singulation Planning for Robotic Bin Picking","volume":"18","author":"Kumbla","year":"2018","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2021011101554885900_CIT0015","first-page":"1437","article-title":"Parameterized Model Predictive Control of a Nonholonomic Mobile Manipulator: A Terminal Constraint-free Approach","author":"Colombo","year":"2019"},{"key":"2021011101554885900_CIT0016","first-page":"V003T04A002","article-title":"Simulation Based on-line Evaluation of Singulation Plans to Handle Perception Uncertainty in Robotic Bin Picking","author":"Kumbla","year":"2017"},{"key":"2021011101554885900_CIT0017","first-page":"2902","article-title":"Search-based Planning for Manipulation with Motion Primitives","author":"Cohen","year":"2010"},{"issue":"2","key":"2021011101554885900_CIT0018","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1177\/0278364913507983","article-title":"Single- and Dual-arm Motion Planning with Heuristic Search","volume":"33","author":"Cohen","year":"2014","journal-title":"Int. J. Rob. Res."},{"key":"2021011101554885900_CIT0019","first-page":"461","article-title":"Motion Planning for Robotic Manipulators with Independent Wrist Joints","author":"Gochev","year":"2014"},{"key":"2021011101554885900_CIT0020","doi-asserted-by":"crossref","DOI":"10.1109\/COASE.2018.8560414","article-title":"Trajectory Planning for Manipulators Operating in Confined Workspaces","author":"Kabir","year":"2018"},{"key":"2021011101554885900_CIT0021","doi-asserted-by":"crossref","DOI":"10.1115\/MSEC2020-8522","article-title":"Incorporating Tool Contact Considerations in Tool-Path Planning for Robotic Operations","volume-title":"ASME Manufacturing Science and Engineering Conference","author":"Bhatt","year":"2020"},{"key":"2021011101554885900_CIT0022","article-title":"Rapidly-Exploring Random Trees: A New Tool for Path Planning","volume-title":"Research Report 9811","author":"Lavalle","year":"1998"},{"issue":"4","key":"2021011101554885900_CIT0023","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces","volume":"12","author":"Kavraki","year":"1996","journal-title":"IEEE. Trans. Rob. Autom."},{"issue":"7","key":"2021011101554885900_CIT0024","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based Algorithms for Optimal Motion Planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Rob. Res."},{"key":"2021011101554885900_CIT0025","first-page":"3067","article-title":"Batch Informed Trees (bit*): Sampling-based Optimal Planning Via the Heuristically Guided Search of Implicit Random Geometric Graphs","volume-title":"Robotics and Automation (ICRA)","author":"Gammell","year":"2015"},{"key":"2021011101554885900_CIT0026","first-page":"2997","article-title":"Informed Rrt*: Optimal Sampling-based Path Planning Focused Via Direct Sampling of An Admissible Ellipsoidal Heuristic","author":"Gammell","year":"2014"},{"issue":"4","key":"2021011101554885900_CIT0027","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1109\/TRO.2018.2830331","article-title":"Informed Sampling for Asymptotically Optimal Path Planning","volume":"34","author":"Gammell","year":"2018","journal-title":"IEEE Trans. Rob."},{"key":"2021011101554885900_CIT0028","first-page":"4569","article-title":"Stomp: Stochastic Trajectory Optimization for Motion Planning","author":"Kalakrishnan","year":"2011"},{"issue":"9","key":"2021011101554885900_CIT0029","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1177\/0278364914528132","article-title":"Motion Planning with Sequential Convex Optimization and Convex Collision Checking","volume":"33","author":"Schulman","year":"2014","journal-title":"Int. J. Rob. Res."},{"key":"2021011101554885900_CIT0030","first-page":"2493","article-title":"Fast Smoothing of Manipulator Trajectories Using Optimal Bounded-acceleration Shortcuts","author":"Hauser","year":"2010"},{"key":"2021011101554885900_CIT0031","first-page":"489","article-title":"Chomp: Gradient Optimization Techniques for Efficient Motion Planning","author":"Ratliff","year":"2009"},{"key":"2021011101554885900_CIT0032","first-page":"9","article-title":"Gaussian Process Motion Planning","author":"Mukadam","year":"2016"},{"key":"2021011101554885900_CIT0033","doi-asserted-by":"crossref","DOI":"10.1109\/COASE.2019.8843126","article-title":"User-guided Path Planning for Redundant Manipulators in Highly Constrained Work Environments","author":"Rajendran","year":"2019"},{"key":"2021011101554885900_CIT0034","doi-asserted-by":"crossref","DOI":"10.1109\/IROS40897.2019.8967865","article-title":"Context-dependent Search for Generating Paths for Redundant Manipulators in Cluttered Environments","author":"Rajendran","year":"2019"},{"key":"2021011101554885900_CIT0035","article-title":"Manipulator Motion Planning for Part Pick-up and Transport Operations From a Moving Base","volume-title":"IEEE Transactions on Automation Science and Engineering (TASE)","author":"Thakar","year":"2020"},{"key":"2021011101554885900_CIT0036","doi-asserted-by":"crossref","DOI":"10.1109\/IROS45743.2020.9340782","article-title":"Accelerating Bi-directional Sampling-based Search for Motion Planning of Non-holonomic Mobile Manipulators","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Thakar","year":"2020"},{"key":"2021011101554885900_CIT0037","first-page":"2529","article-title":"Retraction-based Rrt Planner for Articulated Models","author":"Pan","year":"2010"},{"key":"2021011101554885900_CIT0038","first-page":"4659","article-title":"Spark Prm: Using Rrts Within Prms to Efficiently Explore Narrow Passages","author":"Shi","year":"2014"},{"key":"2021011101554885900_CIT0039","first-page":"7055","article-title":"Rapidly-exploring Random Vines (rrv) for Motion Planning in Configuration Spaces with Narrow Passages","author":"Tahirovic","year":"2018"},{"key":"2021011101554885900_CIT0040","first-page":"4207","article-title":"Regionally Accelerated Batch Informed Trees (rabit*): A Framework to Integrate Local Information Into Optimal Path Planning","author":"Choudhury","year":"2016"},{"key":"2021011101554885900_CIT0041","first-page":"2543","article-title":"Sr-rrt: Selective Retraction-Based Rrt Planner","author":"Junghwan","year":"2012"},{"issue":"6","key":"2021011101554885900_CIT0042","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1109\/TRO.2014.2340191","article-title":"Balancing Exploration and Exploitation in Sampling-Based Motion Planning","volume":"30","author":"Rickert","year":"2014","journal-title":"IEEE Trans. Rob."},{"key":"2021011101554885900_CIT0043","first-page":"477","article-title":"Randomized Path Planning for Redundant Manipulators Without Inverse Kinematics","author":"Weghe","year":"2007"},{"key":"2021011101554885900_CIT0044","article-title":"Bispace Planning: Concurrent Multi-Space Exploration","volume":"63","author":"Diankov","year":"2008","journal-title":"Proc. Rob.: Sci. Syst. IV"},{"key":"2021011101554885900_CIT0045","doi-asserted-by":"crossref","first-page":"7425","DOI":"10.1109\/IROS40897.2019.8967796","article-title":"Bidirectional Heuristic Search for Motion Planning with An Extend Operator","volume-title":"2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Cheng","year":"2019"},{"key":"2021011101554885900_CIT0046","first-page":"453","article-title":"Using Workspace Information As a Guide to Non-uniform Sampling in Probabilistic Roadmap Planners","author":"van den Berg","year":"2004"},{"key":"2021011101554885900_CIT0047","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-540-68405-3_3","article-title":"Workspace-based Connectivity Oracle: An Adaptive Sampling Strategy for Prm Planning","volume":"47","author":"Kurniawati","year":"2006","journal-title":"Springer Tracts Adv. Rob."},{"key":"2021011101554885900_CIT0048","first-page":"3757","article-title":"Adaptive Workspace Biasing for Sampling-based Planners","author":"Zucker","year":"2008"},{"issue":"12","key":"2021011101554885900_CIT0049","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1177\/0278364910396389","article-title":"Task Space Regions: A Framework for Pose-constrained Manipulation Planning","volume":"30","author":"Berenson","year":"2011","journal-title":"Int. J. Rob. Res. (IJRR)"},{"key":"2021011101554885900_CIT0050","first-page":"785","article-title":"Deterministic Motion Planning for Redundant Robots Along End-Effector Paths","author":"Quispe","year":"2012"},{"key":"2021011101554885900_CIT0051","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/IROS.2018.8593870","article-title":"Hierarchical Path Planner Using Workspace Decomposition and Parallel Task-Space Rrts","volume-title":"2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Mesesan","year":"2018"},{"key":"2021011101554885900_CIT0052","first-page":"2864","article-title":"An Effort Bias for Sampling-Based Motion Planning","author":"Kiesel","year":"2017"},{"key":"2021011101554885900_CIT0053","first-page":"6491","article-title":"Prot: Productive Regions Oriented Task Space Path Planning for Hyper-redundant Manipulators","author":"Lee","year":"2014"},{"key":"2021011101554885900_CIT0054","doi-asserted-by":"crossref","first-page":"8606","DOI":"10.1109\/ICRA.2019.8794317","article-title":"Using Local Experiences for Global Motion Planning","volume-title":"2019 International Conference on Robotics and Automation (ICRA)","author":"Chamzas","year":"2019"},{"issue":"1\u20133","key":"2021011101554885900_CIT0055","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1177\/0278364915594029","article-title":"Multi-heuristic a*","volume":"35","author":"Aine","year":"2016","journal-title":"Int. J. Rob. Res."},{"article-title":"Robot Motion Planning in Learned Latent Spaces","year":"2018","author":"Ichter","key":"2021011101554885900_CIT0056"},{"issue":"4","key":"2021011101554885900_CIT0057","doi-asserted-by":"crossref","first-page":"3868","DOI":"10.1109\/LRA.2018.2856927","article-title":"Efficient Sampling Withq-learning to Guide Rapidly Exploring Random Trees","volume":"3","author":"Huh","year":"2018","journal-title":"IEEE Rob. Auto. Lett."},{"key":"2021011101554885900_CIT0058","doi-asserted-by":"crossref","first-page":"6582","DOI":"10.1109\/IROS.2018.8593772","article-title":"Deeply Informed Neural Sampling for Robot Motion Planning","volume-title":"2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Qureshi","year":"2018"},{"key":"2021011101554885900_CIT0059","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1109\/IROS40897.2019.8968503","article-title":"Lego: Leveraging Experience in Roadmap Generation for Sampling-Based Planning","volume-title":"2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Kumar","year":"2019"},{"key":"2021011101554885900_CIT0060","first-page":"2646","article-title":"Machine Learning Guided Exploration for Sampling-based Motion Planning Algorithms","author":"Arslan","year":"2015"},{"key":"2021011101554885900_CIT0061","doi-asserted-by":"crossref","first-page":"3965","DOI":"10.1109\/IROS40897.2019.8968089","article-title":"Neural Path Planning: Fixed Time, Near-optimal Path Generation Via Oracle Imitation","volume-title":"2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Bency","year":"2019"},{"key":"2021011101554885900_CIT0062","doi-asserted-by":"crossref","first-page":"3542","DOI":"10.1109\/IROS40897.2019.8968474","article-title":"Fast Motion Planning Via Free C-space Estimation Based on Deep Neural Network","volume-title":"2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Li","year":"2019"},{"key":"2021011101554885900_CIT0063","first-page":"6490","article-title":"Deep Sequential Models for Sampling-based Planning","author":"Kuo","year":"2018"},{"key":"2021011101554885900_CIT0064","first-page":"12","article-title":"Combining Motion Planning and Optimization for Flexible Robot Manipulation","author":"Scholz","year":"2010"},{"article-title":"dyngraph2vec: Capturing Network Dynamics Using Dynamic Graph Representation Learning","year":"2018","author":"Goyal","key":"2021011101554885900_CIT0065"},{"key":"2021011101554885900_CIT0066","first-page":"995","article-title":"Rrt-connect: An Efficient Approach to Single-query Path Planning","author":"Kuffner","year":"2000"},{"key":"2021011101554885900_CIT0067","first-page":"435","article-title":"Quaternion-Based Kinematic Control of Redundant Spacecraft\/Manipulator Systems","author":"Caccavale","year":"2001"},{"key":"2021011101554885900_CIT0068","first-page":"1478","article-title":"Anytime Motion Planning Using the Rrt*","author":"Karaman","year":"2011"},{"key":"2021011101554885900_CIT0069","first-page":"3859","article-title":"Fcl: A General Purpose Library for Collision and Proximity Queries","author":"Pan","year":"2012"},{"key":"2021011101554885900_CIT0070","first-page":"4371","article-title":"Automated Tuning and Configuration of Path Planning Algorithms","author":"Burger","year":"2017"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4048619\/6613578\/jcise_21_1_011009.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4048619\/6613578\/jcise_21_1_011009.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T21:40:01Z","timestamp":1669066801000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4048619\/1087575\/Strategies-for-Speeding-Up-Manipulator-Path"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,10]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4048619","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2020,12,10]]},"article-number":"011009"}}