New version page

cprm-icra01

Upgrade to remove ads

This preview shows page 1-2 out of 6 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Customizing PRM Roadmaps at Query Time Guang Song Shawna Miller Nancy M. AmatoDepartment of Computer ScienceTexas A&M UniversityCollege Station, TX 77843-3112fgsong,slm5563,[email protected] this paper, we propose a new approach for building andquerying probabilistic roadmaps. In the roadmap constructionstage, we build coarse roadmaps by performing only an approxi-mate validation of the roadmap nodes and/or edges. In the querystage, the roadmap is validated and refined only in the area of in-terest for the query, and moreover, is customized in accordancewith any specified query preferences. This approach, which post-pones some of the validation checks (e.g., collision checks) to thequery phase, yields more efficient solutions to many problems. Animportant benefit of our approach is that it gives one the ability tocustomize the same roadmap in accordance with multiple, vari-able, query preferences. For example, our approach enables oneto find a path which maintains a particular clearance, or makes atmost some specified number of sharp turns. Our preliminary re-sults on problems drawn from diverse application domains showthat this new approach dramatically improves performance, andshows remarkable flexibility when adapting to different query re-quirements.1 IntroductionAutomatic motion planning deals with finding a feasi-ble sequence of motions to take some moving object (the‘robot’) from a given initial configurationto some specifiedgoal configuration. While complete motion planning algo-rithms do exist, they are rarely used in practice since theyare computationally infeasible in all but the simplest cases[14]. For this reason, attention has focused on probabilisticmethods, which sacrifice completeness in favor of compu-tational feasibility and applicability.In particular, a class of algorithms known as as proba-bilistic roadmap (PRM) methods have been the subject ofmuch recent work. These successes sparked a flurry of ac-tivity in whichPRM motion planning techniques were ap-plied to a number of challenging problems arising in a vari-ety of fields including robotics (e.g., closed-chain systems This research supported in part by NSF CAREER Award CCR-9624315 (with REU Supplement), NSF Grants IIS-9619850 (with REUSupplement), ACI-9872126, EIA-9975018, EIA-9805823, and EIA-9810937, and by the Texas Higher Education Coordinating Board undergrant ARP-036327-017.[11, 16]), CAD (e.g., maintainability [3, 8], deformable ob-jects [2, 13]), and even computational Biology and Chem-istry (e.g., ligand docking [18, 4], protein folding [20, 19]).Indeed, it can be argued that thePRM framework was in-strumental in this broadening of the range of applicabilityof motion planning, as many of these problems had neverbefore been considered candidates for automatic methods.At the same time, these new applications served to pointout some weaknesses in thePRM approach. In particular,it was observed that there were some classes of problemsfor whichPRMs did not yield efficient solutions. For exam-ple, problems where the solution path must traverse narrowpassages in C-space [12]. As a result, a number ofPRMvariants specifically targeted at this problem have been pro-posed, e.g., [1, 7, 12]. Also, some novel approaches forimprovingPRM efficiency have shown promising results[6, 17] (these methods do not address the narrow passageproblem). Unfortunately, however,PRM solutions to manyproblems still take prohibitively long.Another shortcoming ofPRMs is that while they are verygood at finding a path, they do not support applicationswhich might impose particular, variable, requirements onthe sought after path, e.g., maintaining a particular clear-ance from obstacles or minimizing the robot’s rotation asit moves. This issue has not received as much attentionas, e.g., the narrow passage problem, because simply find-ing any path was considered a necessary first step in manycases. However, this issue must be addressed beforePRMscan be used in many practical instances.In this work, we propose a new approach for buildingand querying probabilistic roadmaps that addresses boththe above shortcomings of currentPRMs.In the roadmap construction stage, we build coarseroadmaps by performing only approximate validationof roadmap nodes and edges.In the query stage, the roadmap is validated and re-fined only in the area of interest for the query, andmoreover, is customized in accordance with any spec-ified query preferences.This approach, which postpones some of the validationchecks (e.g., collision checks) to the query phase, yieldsmore efficient solutions to many problems. For example,consider a roadmap withnnodes, each of which is con-nected to itsknearest neighbors, who are at an averagedistance ofdfrom it. Constructing this roadmap in itsentirety would requireO(nk d)validity checks – the ma-jority of which are not needed for any particular solutionpath. Our strategy of postponing validation leads to fasterroadmap construction, while incurring only slightly higherquery times. As discussed below, similar strategies havebeen used by other researchers [6, 17].An important benefit of our approach is that it gives onethe ability to customize the roadmap in accordance with anyspecified, variable, query requirements. For example, itmight be specified that the solution path should maintaina certain clearance from the obstacles, that the robot’s rota-tion should be minimized, or that the path should contain atmost some fixed number of bends. And moreover, these re-quirements might change for different queries in the sameroadmap, or might actually be preferences (as opposed torequirements) with different priorities. Using the sameroadmap, one might want several different paths: a pathwith a particular clearance and minimal rotation, a pathwith a desired clearance from obstacles, and another pathwith a different clearance threshold. CurrentPRMs do notsupport such customizable use of the same roadmap.2 Related WorkIn this section we briefly mention other approaches tar-geted at either improving the efficiency ofPRMs or in sup-porting requirements on the query path other than the usualcollision-free requirement. First, there has been some re-cent work aimed at improving the efficiency ofPRMsbypostponingmost of the validation to the query stage [6, 17].LikePRM, Lazy PRM [6] randomly generates nodes inthe configuration space, and edges in the roadmap repre-sent paths between roadmap nodes. UnlikePRM, all nodesand


Download cprm-icra01
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view cprm-icra01 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view cprm-icra01 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?