Koordinované hledání cest s formacemi
| Název práce v češtině: | Koordinované hledání cest s formacemi |
|---|---|
| Název v anglickém jazyce: | Coordinated pathfinding with formations |
| Klíčová slova: | koordinované hledání cest, formace, plánování cest pro mnoho agentů, LRA*, doménově nezávislé plánovače |
| Klíčová slova anglicky: | coordinated pathfinding, formations, multi-agent path planning, LRA*, domain independent planners |
| Akademický rok vypsání: | 2011/2012 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | doc. RNDr. Pavel Surynek, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 10.11.2011 |
| Datum zadání: | 11.11.2011 |
| Datum potvrzení stud. oddělením: | 06.12.2011 |
| Datum a čas obhajoby: | 20.06.2013 00:00 |
| Datum odevzdání elektronické podoby: | 20.05.2013 |
| Datum odevzdání tištěné podoby: | 24.05.2013 |
| Datum proběhlé obhajoby: | 20.06.2013 |
| Oponenti: | RNDr. Tomáš Balyo, Ph.D. |
| Zásady pro vypracování |
| Prostudujte problematiku centrálního koordinovaného hledání cest pro více agentů, jak je ukázáno v [1,2, 4, 5, 6]. Své studium zaměřte na techniky generující sub-optimální řešení vzhledem k celkovému času vykonání plánu (makespan) [3]. Nastudované poznatky využijte k návrhu nové řešící techniky, která bude provádět koordinované plánování cest pro více agentů s udržováním formací. Navrženou techniku implementujte formou softwarového prototypu a proveďte kvalitativní (udržení formace) a kvantitativní (makespan) experimentální srovnání s některým z existujících sub-optimálních řešících algoritmů (například s WHCA*, LRA* [3] či BIBOX [4]). |
| Seznam odborné literatury |
| [1] R. Luna, K. E. Bekris: An Efficient and Complete Approach for Cooperative Path-Finding. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2011), AAAI Press, 2011.
[2] M. R. K. Ryan: Graph Decomposition for Efficient Multi-Robot Path Planning. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 2003-2008, IJCAI Conference, 2007. [3] D. Silver: Cooperative path�nding. Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005), pp. 117-122, AAAI Press, 2005. [4] P. Surynek: An Application of Pebble Motion on Graphs to Abstract Multi-robot Path Planning. Proceedings of the 21st International Conference on Tools with Artificial Intelligence (ICTAI 2009), pp. 151-158, IEEE Press, 2009. [5] P. Surynek: An Optimization Variant of Multi-Robot Path Planning Is Intractable. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), AAAI Press, 2010. [6] K. C. Wang and A. Botea: MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees. Journal of Artificial Intelligence Research, Volume 42, pp. 55-90, AAAI Press, 2011. |
| Předběžná náplň práce |
| Koordinované hledání cest představuje v současnosti velmi aktuální a živé téma v umělé inteligenci. Ačkoli je tato problematika studována již více než 10 let, na několika posledních hlavních konferencích o umělé inteligenci (AAAI 2010, 2011; IJCAI 2011) byly představeny nové efektivní řešící techniky. Práce na tématu tak pro řešitele představuje možnost seznámit se s jedním z hlavních trendů v umělé inteligenci. |
| Předběžná náplň práce v anglickém jazyce |
| Coordinated pathfinding currently represents a topical subject within artificial intelligence. Work on this thesis allows the student to get familiar with one of the main trends of today's artificial intelligence. |