Self-adaptive probabilistic roadmap generation for intelligent virtual agents

Katrina Samperi, Nelly Bencomo, Peter R. Lewis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Agents inhabiting large scale environments are faced with the problem of generating maps by which they can navigate. One solution to this problem is to use probabilistic roadmaps which rely on selecting and connecting a set of points that describe the interconnectivity of free space. However, the time required to generate these maps can be prohibitive, and agents do not typically know the environment in advance. In this paper we show that the optimal combination of different point selection methods used to create the map is dependent on the environment, no point selection method dominates. This motivates a novel self-adaptive approach for an agent to combine several point selection methods. The success rate of our approach is comparable to the state of the art and the generation cost is substantially reduced. Self-adaptation therefore enables a more efficient use of the agent's resources. Results are presented for both a set of archetypal scenarios and large scale virtual environments based in Second Life, representing real locations in London.

Original languageEnglish
Title of host publicationProceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014
Place of PublicationPiscataway, NJ (US)
PublisherIEEE
Pages129-138
Number of pages10
ISBN (Print)978-1-4799-5367-7
DOIs
Publication statusPublished - 5 Jan 2015
EventIEEE 8th international conference on Self-Adaptive and Self-Organizing systems - Imperial College London, London, United Kingdom
Duration: 8 Sep 201412 Sep 2014

Conference

ConferenceIEEE 8th international conference on Self-Adaptive and Self-Organizing systems
Abbreviated titleSASO 2014
CountryUnited Kingdom
CityLondon
Period8/09/1412/09/14
OtherPart of FAS* - Foundation and Applications of Self* Computing Conferences
Collocated with: The International Conference on Cloud and Autonomic Computing (CAC 2014) The 14th IEEE Peer-to-Peer Computing Conference

Fingerprint

Intelligent virtual agents
Virtual reality
Costs

Keywords

  • Map generation
  • Probabilistic Roadmaps
  • Route planning
  • Self-adaptive agents
  • Trails
  • Virtual Environments

Cite this

Samperi, K., Bencomo, N., & Lewis, P. R. (2015). Self-adaptive probabilistic roadmap generation for intelligent virtual agents. In Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014 (pp. 129-138). Piscataway, NJ (US): IEEE. https://doi.org/10.1109/SASO.2014.25
Samperi, Katrina ; Bencomo, Nelly ; Lewis, Peter R. / Self-adaptive probabilistic roadmap generation for intelligent virtual agents. Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014. Piscataway, NJ (US) : IEEE, 2015. pp. 129-138
@inproceedings{99dc5219d8354c94909e3e68a73e7bab,
title = "Self-adaptive probabilistic roadmap generation for intelligent virtual agents",
abstract = "Agents inhabiting large scale environments are faced with the problem of generating maps by which they can navigate. One solution to this problem is to use probabilistic roadmaps which rely on selecting and connecting a set of points that describe the interconnectivity of free space. However, the time required to generate these maps can be prohibitive, and agents do not typically know the environment in advance. In this paper we show that the optimal combination of different point selection methods used to create the map is dependent on the environment, no point selection method dominates. This motivates a novel self-adaptive approach for an agent to combine several point selection methods. The success rate of our approach is comparable to the state of the art and the generation cost is substantially reduced. Self-adaptation therefore enables a more efficient use of the agent's resources. Results are presented for both a set of archetypal scenarios and large scale virtual environments based in Second Life, representing real locations in London.",
keywords = "Map generation, Probabilistic Roadmaps, Route planning, Self-adaptive agents, Trails, Virtual Environments",
author = "Katrina Samperi and Nelly Bencomo and Lewis, {Peter R.}",
year = "2015",
month = "1",
day = "5",
doi = "10.1109/SASO.2014.25",
language = "English",
isbn = "978-1-4799-5367-7",
pages = "129--138",
booktitle = "Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014",
publisher = "IEEE",
address = "United States",

}

Samperi, K, Bencomo, N & Lewis, PR 2015, Self-adaptive probabilistic roadmap generation for intelligent virtual agents. in Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014. IEEE, Piscataway, NJ (US), pp. 129-138, IEEE 8th international conference on Self-Adaptive and Self-Organizing systems, London, United Kingdom, 8/09/14. https://doi.org/10.1109/SASO.2014.25

Self-adaptive probabilistic roadmap generation for intelligent virtual agents. / Samperi, Katrina; Bencomo, Nelly; Lewis, Peter R.

Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014. Piscataway, NJ (US) : IEEE, 2015. p. 129-138.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Self-adaptive probabilistic roadmap generation for intelligent virtual agents

AU - Samperi, Katrina

AU - Bencomo, Nelly

AU - Lewis, Peter R.

PY - 2015/1/5

Y1 - 2015/1/5

N2 - Agents inhabiting large scale environments are faced with the problem of generating maps by which they can navigate. One solution to this problem is to use probabilistic roadmaps which rely on selecting and connecting a set of points that describe the interconnectivity of free space. However, the time required to generate these maps can be prohibitive, and agents do not typically know the environment in advance. In this paper we show that the optimal combination of different point selection methods used to create the map is dependent on the environment, no point selection method dominates. This motivates a novel self-adaptive approach for an agent to combine several point selection methods. The success rate of our approach is comparable to the state of the art and the generation cost is substantially reduced. Self-adaptation therefore enables a more efficient use of the agent's resources. Results are presented for both a set of archetypal scenarios and large scale virtual environments based in Second Life, representing real locations in London.

AB - Agents inhabiting large scale environments are faced with the problem of generating maps by which they can navigate. One solution to this problem is to use probabilistic roadmaps which rely on selecting and connecting a set of points that describe the interconnectivity of free space. However, the time required to generate these maps can be prohibitive, and agents do not typically know the environment in advance. In this paper we show that the optimal combination of different point selection methods used to create the map is dependent on the environment, no point selection method dominates. This motivates a novel self-adaptive approach for an agent to combine several point selection methods. The success rate of our approach is comparable to the state of the art and the generation cost is substantially reduced. Self-adaptation therefore enables a more efficient use of the agent's resources. Results are presented for both a set of archetypal scenarios and large scale virtual environments based in Second Life, representing real locations in London.

KW - Map generation

KW - Probabilistic Roadmaps

KW - Route planning

KW - Self-adaptive agents

KW - Trails

KW - Virtual Environments

UR - http://www.scopus.com/inward/record.url?scp=84936861152&partnerID=8YFLogxK

UR - https://ieeexplore.ieee.org/document/7001008/

U2 - 10.1109/SASO.2014.25

DO - 10.1109/SASO.2014.25

M3 - Conference contribution

SN - 978-1-4799-5367-7

SP - 129

EP - 138

BT - Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014

PB - IEEE

CY - Piscataway, NJ (US)

ER -

Samperi K, Bencomo N, Lewis PR. Self-adaptive probabilistic roadmap generation for intelligent virtual agents. In Proceedings : 2014 IEEE eighth international conference on Self-Adaptive and Self-Organizing systems, SASO 2014. Piscataway, NJ (US): IEEE. 2015. p. 129-138 https://doi.org/10.1109/SASO.2014.25