The Impact of a Bi-connected Graph Decomposition on Solving Cooperative Path-finding Problems

• Autorzy: Surynek P. , Surynková P. , Chromý M.

Identyfikatory

DOI

10.3233/FI-2014-1123

• Języki publikacji: EN

Abstrakty

EN

This paper proposes a framework for analyzing algorithms for inductive processing of bi-connected graphs. The BIBOX algorithm for solving cooperative path-finding problems over biconnected graphs is submitted for the suggested analysis. The algorithm proceeds according to a decomposition of a given bi-connected graph into handles. After finishing a handle, the handle is ruled out of consideration and the processing task is reduced to a task of the same type on a smaller graph. The handle decomposition for which the BIBOX algorithm performs best is theoretically identified. The conducted experimental evaluation confirms that the suggested theoretical analysis well corresponds to the real situation.

Słowa kluczowe

EN

BIBOX algorithm; bi-connected graphs; cooperative path-finding; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 3
• Strony: 295--308
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Surynek P.

• Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské námĕstì 25, 118 00 Praha 1, Czech Republic

autor

Surynková P.

• Department of Mathematics Education Faculty of Mathematics and Physics, Charles University in Prague, Sokolovska 83, 186 75 Praha 8, Czech Republic

autor

Chromý M.

• Faculty of Mathematics and Physics, Charles University in Prague, Malostranské námĕstì 25, 118 00 Praha 1, Czech Republic

Bibliografia

• [1] Cheriton, D., Tarjan, R. E.: Finding Minimum Spanning Trees. SIAM Journal on Computing, Volume 5, pp. 724–741, Society for Industrial and Applied Mathematics, 1976.
• [2] Dijkstra, E. W.: A Note on Two Problems in Connection with Graphs. Numerische Mathematik, Volume 1, pp. 269–271, Springer Verlag, 1959.
• [3] Jarnık, V.: O jistém problému minimálnım (About a Certain Minimal Problem). Práce Moravské Přırodovĕdecké Společnosti, Volume 6, pp. 57–63, Moravská Přırodovĕdecká Společnost, 1930.
• [4] Kornhauser, D., Miller, G. L., and Spirakis, P. G.: Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS 1984), pp. 241-250, IEEE Press, 1984.
• [5] Kruskal, J. B.: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, Volume 7, pp. 48–50, American Mathematical Society, 1956.
• [6] Nešetřìl, J., Milková, E., Nešetřìlová, H. Otakar Boruvka on Minimum Spanning Tree Problem: Translation of both the 1926 Papers, Comments, History. Discrete Mathematics, Volume 233 (1–3), pp. 3–36, Elsevier, 2001.
• [7] Prim, R. C.: Shortest Connection Networks and Some Generalizations. Bell System Technical Journal, Volume 36, pp. 1389–1401, American Telephone and Telegraph Company, 1957.
• [8] Ryan, M. R. K.: Exploiting Subgraph Structure in Multi-Robot Path Planning, Journal of Artificial Intelligence Research (JAIR), Volume 31, pp. 497-542, AAA Press, 2008.
• [9] Silver, D.: Cooperative Pathfinding. Proceedings of the 1st Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005), pp. 117-122, AAAI Press.
• [10] Surynek, P.: A Novel Approach to Path Planning for Multiple Robots in Bi-connected Graphs. Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA 2009), pp. 3613-3619, IEEE Press, 2009.
• [11] Surynek, P.: Solving Abstract Cooperative Path-Finding in Densely Populated Environments. Computational Intelligence (COIN), Volume 30, Issue 2, pp. 402-450, Wiley, 2014.
• [12] Tarjan, R. E.: Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, Volume 1, Number 5-6, pp. 146-160, Society for Industrial and Applied Mathematics, 1972.
• [13] Westbrook, J., Tarjan, R. E.: Maintaining Bridge-connected and Biconnected Components On-line. Algorithmica, Volume 7, Number 5&6, pp. 433–464, Springer Verlag, 1992.
• [14] de Wilde, B., ter Mors, A.,Witteveen, C.: Push and Rotate: Cooperative Multi-agent Path Planning. Proceedings of International conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), IFAAMAS, 2013, pp. 87-94.