A COMBINED UNIFORM AND HEURISTIC SEARCH ALGORITHM FOR MAINTAINING SHORTEST PATHS ON FULLY DYNAMIC GRAPHS
Sandro Castronovo, Björn Kunz, Christian Müller
2012
Abstract
Shortest-path problems on graphs have been studied in depth in Artificial Intelligence and Computer Science. Search on dynamic graphs, i.e. graphs that can change their layout while searching, receives plenty of attention today – mostly in the planning domain. Approaches often assume global knowledge on the dynamic graph, i.e. that topology and dynamic operations are known to the algorithm. There exist use-cases however, where this assumption cannot be made. In vehicular ad-hoc networks, for example, a vehicle is only able to recognize the topology of the graph within wireless network transmission range. In this paper, we propose a combined uniform and heuristic search algorithm, which maintains shortest paths in highly dynamic graphs under the premise that graph operations are not globally known.
DownloadPaper Citation
in Harvard Style
Castronovo S., Kunz B. and Müller C. (2012). A COMBINED UNIFORM AND HEURISTIC SEARCH ALGORITHM FOR MAINTAINING SHORTEST PATHS ON FULLY DYNAMIC GRAPHS . In Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-95-9, pages 119-126. DOI: 10.5220/0003743401190126
in Bibtex Style
@conference{icaart12,
author={Sandro Castronovo and Björn Kunz and Christian Müller},
title={A COMBINED UNIFORM AND HEURISTIC SEARCH ALGORITHM FOR MAINTAINING SHORTEST PATHS ON FULLY DYNAMIC GRAPHS},
booktitle={Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2012},
pages={119-126},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003743401190126},
isbn={978-989-8425-95-9},
}
in EndNote Style
TY - CONF
JO - Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - A COMBINED UNIFORM AND HEURISTIC SEARCH ALGORITHM FOR MAINTAINING SHORTEST PATHS ON FULLY DYNAMIC GRAPHS
SN - 978-989-8425-95-9
AU - Castronovo S.
AU - Kunz B.
AU - Müller C.
PY - 2012
SP - 119
EP - 126
DO - 10.5220/0003743401190126