Ontology type: schema:ScholarlyArticle
2018-07
AUTHORSMichael Morin, Margarita P. Castro, Kyle E. C. Booth, Tony T. Tran, Chang Liu, J. Christopher Beck
ABSTRACTWe develop optimization approaches to the graph-clear problem, a pursuit-evasion problem where mobile robots must clear a facility of intruders. The objective is to minimize the number of robots required. We contribute new formal results on progressive and contiguous assumptions and their impact on algorithm completeness. We present mixed-integer linear programming and constraint programming models, as well as new heuristic variants for the problem, comparing them to previously proposed heuristics. Our empirical work indicates that our heuristic variants improve on those from the literature, that constraint programming finds better solutions than the heuristics in run-times reasonable for the application, and that mixed-integer linear programming is superior for proving optimality. Given their performance and the appeal of the model-and-solve framework, we conclude that the proposed optimization methods are currently the most suitable for the graph-clear problem. More... »
PAGES335-354
http://scigraph.springernature.com/pub.10.1007/s10601-018-9288-3
DOIhttp://dx.doi.org/10.1007/s10601-018-9288-3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1104134112
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/0803",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computer Software",
"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": "University of Toronto",
"id": "https://www.grid.ac/institutes/grid.17063.33",
"name": [
"Department of Operations and Decision Support Systems, Universit\u00e9 Laval, Qu\u00e9bec, QC, Canada",
"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Morin",
"givenName": "Michael",
"id": "sg:person.010040734127.43",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010040734127.43"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Toronto",
"id": "https://www.grid.ac/institutes/grid.17063.33",
"name": [
"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Castro",
"givenName": "Margarita P.",
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Toronto",
"id": "https://www.grid.ac/institutes/grid.17063.33",
"name": [
"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Booth",
"givenName": "Kyle E. C.",
"id": "sg:person.016247021735.24",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016247021735.24"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Toronto",
"id": "https://www.grid.ac/institutes/grid.17063.33",
"name": [
"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Tran",
"givenName": "Tony T.",
"id": "sg:person.07543750535.57",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07543750535.57"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Toronto",
"id": "https://www.grid.ac/institutes/grid.17063.33",
"name": [
"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Liu",
"givenName": "Chang",
"id": "sg:person.014361537240.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014361537240.48"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Toronto",
"id": "https://www.grid.ac/institutes/grid.17063.33",
"name": [
"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Beck",
"givenName": "J. Christopher",
"id": "sg:person.011702761017.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011702761017.45"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1023/a:1015256330750",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002320955",
"https://doi.org/10.1023/a:1015256330750"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10514-011-9241-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003803092",
"https://doi.org/10.1007/s10514-011-9241-4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-84628-974-3_38",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014811039",
"https://doi.org/10.1007/978-1-84628-974-3_38"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-84628-974-3_38",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014811039",
"https://doi.org/10.1007/978-1-84628-974-3_38"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.3182/20140824-6-za-1003.02476",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021694010"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(86)90146-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023492229"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(86)90146-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023492229"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-22416-9_26",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033238501",
"https://doi.org/10.1007/978-3-319-22416-9_26"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0070400",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036228874",
"https://doi.org/10.1007/bfb0070400"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-44953-1_34",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036629343",
"https://doi.org/10.1007/978-3-319-44953-1_34"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(78)90029-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041340635"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.tcs.2008.02.040",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042364695"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/rsa.20275",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044664736"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/rsa.20275",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044664736"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/564870.564906",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051619886"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tro.2009.2035737",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061785106"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tsmcc.2004.840051",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061797791"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/iros.2007.4399368",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093523590"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icsmc.1999.812514",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093660496"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/iros.2008.4650763",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094482705"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/robot.2008.4543566",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095233900"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icra.2012.6225234",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095259690"
],
"type": "CreativeWork"
}
],
"datePublished": "2018-07",
"datePublishedReg": "2018-07-01",
"description": "We develop optimization approaches to the graph-clear problem, a pursuit-evasion problem where mobile robots must clear a facility of intruders. The objective is to minimize the number of robots required. We contribute new formal results on progressive and contiguous assumptions and their impact on algorithm completeness. We present mixed-integer linear programming and constraint programming models, as well as new heuristic variants for the problem, comparing them to previously proposed heuristics. Our empirical work indicates that our heuristic variants improve on those from the literature, that constraint programming finds better solutions than the heuristics in run-times reasonable for the application, and that mixed-integer linear programming is superior for proving optimality. Given their performance and the appeal of the model-and-solve framework, we conclude that the proposed optimization methods are currently the most suitable for the graph-clear problem.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10601-018-9288-3",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1043977",
"issn": [
"1383-7133",
"1572-9354"
],
"name": "Constraints",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "23"
}
],
"name": "Intruder alert! Optimization models for solving the mobile robot graph-clear problem",
"pagination": "335-354",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"57194be0f624a193bea3ce48b0e5d5d3b41f64dfc6530c67979e47fcbc714ace"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10601-018-9288-3"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1104134112"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10601-018-9288-3",
"https://app.dimensions.ai/details/publication/pub.1104134112"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T10:03",
"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/0000000347_0000000347/records_89824_00000003.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs10601-018-9288-3"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s10601-018-9288-3'
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/s10601-018-9288-3'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9288-3'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9288-3'
This table displays all metadata directly associated to this object as RDF triples.
159 TRIPLES
21 PREDICATES
46 URIs
19 LITERALS
7 BLANK NODES