Distributed Map Construction

Assume that two sub-graphs of a graph are available and that the graph represents the corridors in a building. Without using any previous knowledge on the entire graph, can these two sub-graphs be used to construct an extended view on the entire graph. To test this assumption a collection of algorithms will be designed and implemented which can fuse two sub-graphs (topological maps) together to achieve this extended view on the unknown environment. The main goal for this project will consist of the distributed construction of topological maps within a simulated environment, with the main focus on the used algorithm(s) for the fusion of multiple maps. This will be realized with the help of a “graph” data structure, a multi agent system and match and merge algorithms. In general the simulated environment will function as a test environment for the algorithms. A real life situation for the simulation environment could be, that it represents a building in which an emergent situation has occurred and in which individuals are exploring the unknown layout of the building in search for their personal goal(s). This system can be used by first responders who are exploring the building and are in search of casualties in case of a fire or a terrorist attack. This will all result in a simulation in which it is assumed that each explorer in the field is equipped with a Personal Digital Assistant (PDA) or a different handheld device and can communicate with the other explorers within its communication range, without the help of a centralized communication system. The explorer’s traveled path is stored into their personal PDA and the software running on the PDA’s shows the explorers their traveled path and if possible combines their map with the received map from the explorers they encounter. If a combination is possible the software on the explores PDA executes the algorithms to construct the most complete view on the environment as possible. The completed or partially completed map can also provide guidance to the explorers if this is needed.MediamaticsElectrical Engineering, Mathematics and Computer Scienc