Coping with Uncertainty in Map Learning View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1997-10

AUTHORS

Kenneth Basye, Thomas Dean, Jeffrey Scott Vitter

ABSTRACT

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one approach, the effects of accumulated error are eliminated by the use of local sensing methods that never mislead but occasionally fail to produce an answer. In another approach, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems. More... »

PAGES

65-88

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1007418008480

DOI

http://dx.doi.org/10.1023/a:1007418008480

DIMENSIONS

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


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": "Clark University", 
          "id": "https://www.grid.ac/institutes/grid.254277.1", 
          "name": [
            "Department of Mathematics and Computer Science, Clark University, 01610, Worcester, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Basye", 
        "givenName": "Kenneth", 
        "id": "sg:person.014372431527.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014372431527.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912, Providence, RI"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dean", 
        "givenName": "Thomas", 
        "id": "sg:person.013717206755.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013717206755.65"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1177/027836498600500404", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016849121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1177/027836498600500404", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016849121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1207/s15516709cog0202_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019604196"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1207/s15516709cog0202_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019604196"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/inco.1994.1081", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026272302"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1117/12.948950", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028842704"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1968.1972", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038881641"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(84)90045-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039936008"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(84)90045-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039936008"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/01621459.1963.10500830", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1058299773"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/70.105395", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061215884"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1979.39", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086237806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1979.34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086254113"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997-10", 
    "datePublishedReg": "1997-10-01", 
    "description": "In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one approach, the effects of accumulated error are eliminated by the use of local sensing methods that never mislead but occasionally fail to produce an answer. In another approach, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1007418008480", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1125588", 
        "issn": [
          "0885-6125", 
          "1573-0565"
        ], 
        "name": "Machine Learning", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "29"
      }
    ], 
    "name": "Coping with Uncertainty in Map Learning", 
    "pagination": "65-88", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4ac4cdd7f9beac1c44f21de9d568663b3e064e76b41a8f90c8a85478eeef8c1d"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1007418008480"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015692664"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1007418008480", 
      "https://app.dimensions.ai/details/publication/pub.1015692664"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T19:06", 
    "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_8678_00000499.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023/A:1007418008480"
  }
]
 

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.1023/a:1007418008480'

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.1023/a:1007418008480'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1007418008480'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1007418008480'


 

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

111 TRIPLES      21 PREDICATES      37 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1007418008480 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nf5cda52b15214697b5becd39b8b094f1
4 schema:citation https://doi.org/10.1006/inco.1994.1081
5 https://doi.org/10.1016/0004-3702(84)90045-6
6 https://doi.org/10.1080/01621459.1963.10500830
7 https://doi.org/10.1109/70.105395
8 https://doi.org/10.1109/sfcs.1979.34
9 https://doi.org/10.1109/sfcs.1979.39
10 https://doi.org/10.1117/12.948950
11 https://doi.org/10.1145/1968.1972
12 https://doi.org/10.1177/027836498600500404
13 https://doi.org/10.1207/s15516709cog0202_3
14 schema:datePublished 1997-10
15 schema:datePublishedReg 1997-10-01
16 schema:description In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one approach, the effects of accumulated error are eliminated by the use of local sensing methods that never mislead but occasionally fail to produce an answer. In another approach, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems.
17 schema:genre research_article
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N362a92973a09426ead54894271b10d9c
21 Nf9bb836d8a624adeb520b9d8bb261b5b
22 sg:journal.1125588
23 schema:name Coping with Uncertainty in Map Learning
24 schema:pagination 65-88
25 schema:productId N1517c62a6eb544a19f78399b11ef0837
26 Nb287d01704f5417dbaed2479fb7eb633
27 Nfe1347309822470482efb4078036a70c
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015692664
29 https://doi.org/10.1023/a:1007418008480
30 schema:sdDatePublished 2019-04-10T19:06
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N7f1d925a9a71475c9aba7628f1649e4e
33 schema:url http://link.springer.com/10.1023/A:1007418008480
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N1517c62a6eb544a19f78399b11ef0837 schema:name dimensions_id
38 schema:value pub.1015692664
39 rdf:type schema:PropertyValue
40 N362a92973a09426ead54894271b10d9c schema:issueNumber 1
41 rdf:type schema:PublicationIssue
42 N7f1d925a9a71475c9aba7628f1649e4e schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 Nb287d01704f5417dbaed2479fb7eb633 schema:name readcube_id
45 schema:value 4ac4cdd7f9beac1c44f21de9d568663b3e064e76b41a8f90c8a85478eeef8c1d
46 rdf:type schema:PropertyValue
47 Nb480a3166a944d93bf3b559f16fc0a1c rdf:first sg:person.0613677314.28
48 rdf:rest rdf:nil
49 Nec918ad7886a4d81a397f67af1d850ea rdf:first sg:person.013717206755.65
50 rdf:rest Nb480a3166a944d93bf3b559f16fc0a1c
51 Nf5cda52b15214697b5becd39b8b094f1 rdf:first sg:person.014372431527.37
52 rdf:rest Nec918ad7886a4d81a397f67af1d850ea
53 Nf9bb836d8a624adeb520b9d8bb261b5b schema:volumeNumber 29
54 rdf:type schema:PublicationVolume
55 Nfe1347309822470482efb4078036a70c schema:name doi
56 schema:value 10.1023/a:1007418008480
57 rdf:type schema:PropertyValue
58 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
59 schema:name Information and Computing Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
62 schema:name Artificial Intelligence and Image Processing
63 rdf:type schema:DefinedTerm
64 sg:journal.1125588 schema:issn 0885-6125
65 1573-0565
66 schema:name Machine Learning
67 rdf:type schema:Periodical
68 sg:person.013717206755.65 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
69 schema:familyName Dean
70 schema:givenName Thomas
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013717206755.65
72 rdf:type schema:Person
73 sg:person.014372431527.37 schema:affiliation https://www.grid.ac/institutes/grid.254277.1
74 schema:familyName Basye
75 schema:givenName Kenneth
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014372431527.37
77 rdf:type schema:Person
78 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
79 schema:familyName Vitter
80 schema:givenName Jeffrey Scott
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
82 rdf:type schema:Person
83 https://doi.org/10.1006/inco.1994.1081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026272302
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/0004-3702(84)90045-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039936008
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1080/01621459.1963.10500830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058299773
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1109/70.105395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061215884
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1109/sfcs.1979.34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086254113
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1109/sfcs.1979.39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086237806
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1117/12.948950 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028842704
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1145/1968.1972 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038881641
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1177/027836498600500404 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016849121
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1207/s15516709cog0202_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019604196
102 rdf:type schema:CreativeWork
103 https://www.grid.ac/institutes/grid.254277.1 schema:alternateName Clark University
104 schema:name Department of Mathematics and Computer Science, Clark University, 01610, Worcester, MA
105 rdf:type schema:Organization
106 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
107 schema:name Department of Computer Science, Duke University, 27708, Durham, NC
108 rdf:type schema:Organization
109 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
110 schema:name Department of Computer Science, Brown University, 02912, Providence, RI
111 rdf:type schema:Organization
 




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


...