|[samperietal2013cave] Kat Samperi, Nick Hawes and Russell Beale. Improving Map Generation in Large-Scale Environments for Intelligent Virtual Agents. In The AAMAS-2013 Workshop on Cognitive Agents for Virtual Environments (CAVE-2013). May 2013. [pdf] [bib]|
Intelligent virtual agents are increasingly faced with very large scale, unstructured environments. In the case of user generated worlds, it is not always possible to give an agent the opportunity to pre-process the map. These agents are required to build a map of their environment and use it to plan routes in a very short period of time.
We look at a new method for improving the generation of roadmaps in these environments using trails. Roadmaps are an abstract type of map showing points the agent can visit and the routes between them. Trails are a list of observations about how other (human and AI controlled) avatars move from place to place. We look at using this trail information to build better roadmaps. A more useful map will be generated in a short period of time and will allow for a higher proportion of routes to be planned while keeping the length of the subsequent route low.
We discovered that trails, when used in conjunction with random point selection did improve the map generation. Trail based maps were able to halve the generation time while still planning short paths and keeping a 100% success when planning a route between a given set of points.
We conclude that trails are a useful tool for generating roadmaps, allowing our intelligent virtual agent to quickly generate and use maps in new, large scale environments.
|Download: pdf (1.55 MB) bib|
|Links: [Google Scholar] [CiteSeer]|