Self-adaptive probabilistic roadmap generation for intelligent virtual agents

Katrina Samperi, Nelly Bencomo, Peter R. Lewis

Research output: Chapter in Book/Published conference outputConference publication


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)
Number of pages10
ISBN (Print)978-1-4799-5367-7
Publication statusPublished - 5 Jan 2015
EventIEEE 8th international conference on Self-Adaptive and Self-Organizing systems - Imperial College London, London, United Kingdom
Duration: 8 Sept 201412 Sept 2014


ConferenceIEEE 8th international conference on Self-Adaptive and Self-Organizing systems
Abbreviated titleSASO 2014
Country/TerritoryUnited Kingdom
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


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


Dive into the research topics of 'Self-adaptive probabilistic roadmap generation for intelligent virtual agents'. Together they form a unique fingerprint.

Cite this