RESAMPL: A Region-Sensitive Adaptive Motion Planner View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Samuel Rodriguez , Shawna Thomas , Roger Pearce , Nancy M. Amato

ABSTRACT

Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (prms) or rapidly-exploring random trees (rrt), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. In this work, we present resampl, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, resampl classifies regions based on the entropy of the samples in it, and then uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing resampl to previous multi-query and single-query methods show that resampl is generally significantly faster and also usually requires fewer samples to solve the problem. More... »

PAGES

285-300

References to SciGraph publications

  • 2005. A Machine Learning Approach for Feature-Sensitive Motion Planning in ALGORITHMIC FOUNDATIONS OF ROBOTICS VI
  • Book

    TITLE

    Algorithmic Foundation of Robotics VII

    ISBN

    978-3-540-68404-6
    978-3-540-68405-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-68405-3_18

    DOI

    http://dx.doi.org/10.1007/978-3-540-68405-3_18

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1017096150


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Texas A&M University", 
              "id": "https://www.grid.ac/institutes/grid.264756.4", 
              "name": [
                "Parasol Lab, Department of Computer Science, Texas A&M University, College Station, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rodriguez", 
            "givenName": "Samuel", 
            "id": "sg:person.07705453505.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07705453505.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Texas A&M University", 
              "id": "https://www.grid.ac/institutes/grid.264756.4", 
              "name": [
                "Parasol Lab, Department of Computer Science, Texas A&M University, College Station, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Thomas", 
            "givenName": "Shawna", 
            "id": "sg:person.014576651641.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014576651641.39"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Texas A&M University", 
              "id": "https://www.grid.ac/institutes/grid.264756.4", 
              "name": [
                "Parasol Lab, Department of Computer Science, Texas A&M University, College Station, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pearce", 
            "givenName": "Roger", 
            "id": "sg:person.011012076601.92", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011012076601.92"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Texas A&M University", 
              "id": "https://www.grid.ac/institutes/grid.264756.4", 
              "name": [
                "Parasol Lab, Department of Computer Science, Texas A&M University, College Station, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Amato", 
            "givenName": "Nancy M.", 
            "id": "sg:person.0611744534.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0611744534.28"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/10991541_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007666438", 
              "https://doi.org/10.1007/10991541_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/237170.237244", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032842816"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/70.508439", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061216299"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/70.864240", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061216782"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/robot.1999.772447", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093319537"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/robot.2005.1570765", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093434145"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/robot.2005.1570590", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094133310"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/robot.2000.844107", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094622948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/robot.2005.1570712", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094731137"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/iros.2001.973336", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095146675"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.15607/rss.2005.i.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099124510"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.15607/rss.2005.i.015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099124522"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (prms) or rapidly-exploring random trees (rrt), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. In this work, we present resampl, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, resampl classifies regions based on the entropy of the samples in it, and then uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing resampl to previous multi-query and single-query methods show that resampl is generally significantly faster and also usually requires fewer samples to solve the problem.", 
        "editor": [
          {
            "familyName": "Akella", 
            "givenName": "Srinivas", 
            "type": "Person"
          }, 
          {
            "familyName": "Amato", 
            "givenName": "Nancy M.", 
            "type": "Person"
          }, 
          {
            "familyName": "Huang", 
            "givenName": "Wesley H.", 
            "type": "Person"
          }, 
          {
            "familyName": "Mishra", 
            "givenName": "Bud", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-68405-3_18", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-68404-6", 
            "978-3-540-68405-3"
          ], 
          "name": "Algorithmic Foundation of Robotics VII", 
          "type": "Book"
        }, 
        "name": "RESAMPL: A Region-Sensitive Adaptive Motion Planner", 
        "pagination": "285-300", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-68405-3_18"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "51741027ed6e512d69c7d440cb69c5de92743693ac540b4a1d2239dacb63faba"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1017096150"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-68405-3_18", 
          "https://app.dimensions.ai/details/publication/pub.1017096150"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T19:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8684_00000253.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-68405-3_18"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-68405-3_18'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-68405-3_18'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-68405-3_18'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-68405-3_18'


     

    This table displays all metadata directly associated to this object as RDF triples.

    138 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-68405-3_18 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N6a284beee53d44a3af76c104c19ed5db
    4 schema:citation sg:pub.10.1007/10991541_25
    5 https://doi.org/10.1109/70.508439
    6 https://doi.org/10.1109/70.864240
    7 https://doi.org/10.1109/iros.2001.973336
    8 https://doi.org/10.1109/robot.1999.772447
    9 https://doi.org/10.1109/robot.2000.844107
    10 https://doi.org/10.1109/robot.2005.1570590
    11 https://doi.org/10.1109/robot.2005.1570712
    12 https://doi.org/10.1109/robot.2005.1570765
    13 https://doi.org/10.1145/237170.237244
    14 https://doi.org/10.15607/rss.2005.i.004
    15 https://doi.org/10.15607/rss.2005.i.015
    16 schema:datePublished 2008
    17 schema:datePublishedReg 2008-01-01
    18 schema:description Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (prms) or rapidly-exploring random trees (rrt), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. In this work, we present resampl, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, resampl classifies regions based on the entropy of the samples in it, and then uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing resampl to previous multi-query and single-query methods show that resampl is generally significantly faster and also usually requires fewer samples to solve the problem.
    19 schema:editor Nfa473cf37c4c4da1b946a0e67ee3540f
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N70a84b1d48b943b5a98c10c2ffb034c4
    24 schema:name RESAMPL: A Region-Sensitive Adaptive Motion Planner
    25 schema:pagination 285-300
    26 schema:productId N89c0863526594c539babe1048e8f1582
    27 N8c4caddb6fbc49d6aeef80c8d0846023
    28 Ncef8e477bd024dadbdb97f6f9eb37372
    29 schema:publisher N9a12e3cbb2394f56977ad398a28dbe7b
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017096150
    31 https://doi.org/10.1007/978-3-540-68405-3_18
    32 schema:sdDatePublished 2019-04-15T19:08
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N636275775b9a4fb78c0e80dee0003042
    35 schema:url http://link.springer.com/10.1007/978-3-540-68405-3_18
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N009dd085203048d19645ef35b52dd965 schema:familyName Amato
    40 schema:givenName Nancy M.
    41 rdf:type schema:Person
    42 N09245c3c55d346e9905f970b6e489b89 rdf:first sg:person.014576651641.39
    43 rdf:rest Ncbd5ef821ecd44d6afb520a42bd51771
    44 N177b7c2ddbdd48d29cf76652dbf45737 rdf:first N009dd085203048d19645ef35b52dd965
    45 rdf:rest Na684b48db3314d4da7e6648a3cef3fc9
    46 N2bff5c109a3a4e9593a7e645351ba58a rdf:first N44fa42f34eb54ae1a1519ae6705f013c
    47 rdf:rest rdf:nil
    48 N2e736937c4ee4c7db721388ad7a15498 schema:familyName Akella
    49 schema:givenName Srinivas
    50 rdf:type schema:Person
    51 N44fa42f34eb54ae1a1519ae6705f013c schema:familyName Mishra
    52 schema:givenName Bud
    53 rdf:type schema:Person
    54 N636275775b9a4fb78c0e80dee0003042 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 N6a284beee53d44a3af76c104c19ed5db rdf:first sg:person.07705453505.08
    57 rdf:rest N09245c3c55d346e9905f970b6e489b89
    58 N6b7b5e30e51946718856a31795593cda rdf:first sg:person.0611744534.28
    59 rdf:rest rdf:nil
    60 N70a84b1d48b943b5a98c10c2ffb034c4 schema:isbn 978-3-540-68404-6
    61 978-3-540-68405-3
    62 schema:name Algorithmic Foundation of Robotics VII
    63 rdf:type schema:Book
    64 N89c0863526594c539babe1048e8f1582 schema:name dimensions_id
    65 schema:value pub.1017096150
    66 rdf:type schema:PropertyValue
    67 N8c4caddb6fbc49d6aeef80c8d0846023 schema:name doi
    68 schema:value 10.1007/978-3-540-68405-3_18
    69 rdf:type schema:PropertyValue
    70 N9a12e3cbb2394f56977ad398a28dbe7b schema:location Berlin, Heidelberg
    71 schema:name Springer Berlin Heidelberg
    72 rdf:type schema:Organisation
    73 Na684b48db3314d4da7e6648a3cef3fc9 rdf:first Nc986ef5b3521419aaa3fb1afe49b21c5
    74 rdf:rest N2bff5c109a3a4e9593a7e645351ba58a
    75 Nc986ef5b3521419aaa3fb1afe49b21c5 schema:familyName Huang
    76 schema:givenName Wesley H.
    77 rdf:type schema:Person
    78 Ncbd5ef821ecd44d6afb520a42bd51771 rdf:first sg:person.011012076601.92
    79 rdf:rest N6b7b5e30e51946718856a31795593cda
    80 Ncef8e477bd024dadbdb97f6f9eb37372 schema:name readcube_id
    81 schema:value 51741027ed6e512d69c7d440cb69c5de92743693ac540b4a1d2239dacb63faba
    82 rdf:type schema:PropertyValue
    83 Nfa473cf37c4c4da1b946a0e67ee3540f rdf:first N2e736937c4ee4c7db721388ad7a15498
    84 rdf:rest N177b7c2ddbdd48d29cf76652dbf45737
    85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Information and Computing Sciences
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Artificial Intelligence and Image Processing
    90 rdf:type schema:DefinedTerm
    91 sg:person.011012076601.92 schema:affiliation https://www.grid.ac/institutes/grid.264756.4
    92 schema:familyName Pearce
    93 schema:givenName Roger
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011012076601.92
    95 rdf:type schema:Person
    96 sg:person.014576651641.39 schema:affiliation https://www.grid.ac/institutes/grid.264756.4
    97 schema:familyName Thomas
    98 schema:givenName Shawna
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014576651641.39
    100 rdf:type schema:Person
    101 sg:person.0611744534.28 schema:affiliation https://www.grid.ac/institutes/grid.264756.4
    102 schema:familyName Amato
    103 schema:givenName Nancy M.
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0611744534.28
    105 rdf:type schema:Person
    106 sg:person.07705453505.08 schema:affiliation https://www.grid.ac/institutes/grid.264756.4
    107 schema:familyName Rodriguez
    108 schema:givenName Samuel
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07705453505.08
    110 rdf:type schema:Person
    111 sg:pub.10.1007/10991541_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007666438
    112 https://doi.org/10.1007/10991541_25
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1109/70.508439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061216299
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1109/70.864240 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061216782
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1109/iros.2001.973336 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095146675
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1109/robot.1999.772447 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093319537
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1109/robot.2000.844107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094622948
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1109/robot.2005.1570590 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094133310
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1109/robot.2005.1570712 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094731137
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1109/robot.2005.1570765 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093434145
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/237170.237244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032842816
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.15607/rss.2005.i.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099124510
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.15607/rss.2005.i.015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099124522
    135 rdf:type schema:CreativeWork
    136 https://www.grid.ac/institutes/grid.264756.4 schema:alternateName Texas A&M University
    137 schema:name Parasol Lab, Department of Computer Science, Texas A&M University, College Station, TX, USA
    138 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...