Requirements
      • The roadmap 
          –is resolution complete
          –is small
          –contains useful cycles
          –provides high-clearance paths
          res. complete, small     useful cycles     high-clearance paths
                                                
    Outline
    • Reachability Roadmap Method (RRM)
      –Resolution complete roadmap
      –Small roadmap
    • Adding useful cycles
    • Adding clearance to the roadmap
    • Experiments
    • Conclusions & current work
                            
    RRM – Criteria
    • Coverage
        – Each free sample can be 
          connected to a vertex in the 
          graph
    • Maximal connectivity
        – For each two vertices v’,v’’:
           • If there exists a path 
            between v’ and v’’ in the 
            free space, then there 
            exists a path between v’ 
            and v’’ in the graph
                                  
     Reachability Roadmap Method
     • Paper
        – R. Geraerts and M.H. Overmars. Creating small 
          roadmaps for solving motion planning problems. 
          MMAR 2005, pp. 531-536 
     • Outline of algorithm
        –Discretizes the free space
        –Computes small set of guards 
        –Guards are connected via connector
        –Resulting roadmap is pruned
                                     
     Adding Useful Cycles
     • Paper
        – D. Nieuwenhuisen and M.H. Overmars. Useful cycles in 
          probabilistic roadmap graphs. ICRA 2004, pp. 446-452
     • Useful edge
        –Edge (v,v’) is K-useful if K * d(v,v’) < G(v,v’)
                v’              v