251. Separating a walkable environment into layers
- Author
-
Hillebrand, Arne, Van Den Akker, Marjan, Geraerts, Roland, Hoogeveen, Han, Spencer, Stephen N., Sub Computer Graphics, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
Optimization ,Mathematical optimization ,021103 operations research ,Linear programming ,business.industry ,Computer science ,Heuristic ,0211 other engineering and technologies ,020207 software engineering ,Multi-layered environment ,02 engineering and technology ,computer.software_genre ,Computer Graphics and Computer-Aided Design ,Human-Computer Interaction ,Set (abstract data type) ,Virtual machine ,0202 electrical engineering, electronic engineering, information engineering ,Local search (optimization) ,business ,Heuristics ,Representation (mathematics) ,Algorithm ,computer ,Software ,Integer (computer science) - Abstract
A multi-layered environment (MLE) [van Toll et al. 2011] is a representation of the walkable environment (WE) in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings, or for finding the shortest routes. The running times of these algorithms depend on the number of connections. Finding an environment with the smallest number of connections, is an NP-Hard problem [Hillebrand et al. 2016]. Our first algorithm tackles this problem by using an integer linear program which is capable of finding the best possible solution, but naturally takes a long time. Hence, we provide two heuristics that search for MLEs with a low number of connections. One algorithm uses local search to gradually improve the found solution. The other one, called the height heuristic, is very fast and gives good solutions in practical environments.
- Published
- 2016