doc. RNDr. Pavel Surynek, Ph.D.

Pracoviště
ČVUT FIT, Katedra aplikované matematiky
Osobní stránky
http://users.fit.cvut.cz/~surynek
E-mail
pavel.surynek@fit.cvut.cz
Telefon
+420 22435 9910

Řešení úloh v umělé inteligenci pomocí redukce na problém splnitelnosti

Solving Problems in Artificial Intelligence by Reduction to Satisfiability

Výzkum v rámci tohoto tématu bude zaměřen na hledání řešení vybraných problémů v umělé inteligenci pomocí redukce na problém splnitelnosti [1]. Mezi problémy, které přestavují vhodné kandidáty pro tento způsob řešení, patří doménově závislé plánování (například hledání cest, plánování pro roboty) [2], rozvrhování, návrh obvodů, nebo kombinatorické úlohy. Pojem splnitelnost zde chápeme v širším smyslu, tj. nikoli pouze jako základní výrokovou splnitelnost (problém SAT), ale zahrnujeme i obecnější splňování podmínek (constraint satisfaction) [3], či kombinace splnitelnosti v různých logických teoriích (SAT-modulo theory – SMT) [4].

Research in this topic will focus on finding solutions to selected problems in artificial intelligence by reduction to satisfiability [1]. Problems representing suitable candidates for this approach include domain-dependent planning (such path-finding, robot planning) [2], scheduling, circuit design, or combinatorial tasks. The concept of satisfiability is understood here in the broader sense, that is, not only as the basic propositional satisfiability (SAT problem), but also as constraint satisfaction [3] or a combination of satisfiability in various logic theories (SAT-modulo theory - SMT) [4].

Reference

  1. Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications 185, IOS Press 2009.
  2. Pavel Surynek: Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems. Ann. Math. Artif. Intell. 81(3-4): pp. 329-375, 2017.
  3. Francesca Rossi, Peter van Beek, Toby Walsh: Handbook of Constraint Programming. Foundations of Artificial Intelligence 2, Elsevier 2006.
  4. Daniel Kroening, Ofer Strichman: Decision Procedures - An Algorithmic Point of View, Second Edition. Texts in Theoretical Computer Science. An EATCS Series, Springer 2016.

Techniky a algoritmy pro multi-agentní hledání cest

Techniques and Algorithms for Multi-agent Path Finding

Cílem výzkumu je návrh nových konceptů a souvisejících řešících algoritmů pro multi-agentní hledání cest (Multi-Agent Path Finding) [1]. V základní variantě problému MAPF hledáme cesty pro agenty pohybující se po neorientovaném grafu tak, aby každý agent dorazil do svého cíle ze zadané počáteční pozice, a přitom se nesrazil s žádným jiným agentem. Současné řešící techniky pro MAPF zahrnují škálu metod od sub-optimálních polynomiálních algoritmů [2] přes optimální algoritmy založené na prohledávání stavového prostoru [3] po transformace do jiných formalismů jako je SAT [4]. Otevřené otázky nabízejí zejména zobecněné varianty problému MAPF, kde uvažujeme navíc například komplexnější vzájemné vyhýbání, udržování formací, souvislosti či jiných globálních vlastností (vlastnost jež zahrnuje všechny agenty), zobecněné cenové funkce či více nezávislých (soupeřících) týmů agentů.

The aim of the research is to design new concepts and related solving algorithms for Multi-Agent Path Finding [1]. The basic variant of the MAPF problem takes place on the undirected graph with agents placed in vertices. We are searching paths for individual agents so that each agent can reache its goal from the specified starting position by following its path and does not collide with any other agent. Contemporary solving techniques for MAPF include a variety of methods ranging from sub-optimal polynomial algorithms [2] through optimal algorithms based on state space search [3] to transformations into different formalisms such as SAT [4]. The open questions offer, in particular, generalized variants of MAPF, where we consider more complex avoidance, maintenance of formations, connectivity maintenance or other global properties (a property that includes all agents), generalized cost functions, or multiple independent (adversarial) teams of agents.

Reference

  1. David Silver, “Cooperative pathfinding,” Proceedings of AIIDE, pp. 117–122, 2005.
  2. Boris de Wilde, Adriaan ter Mors, Cees Witteveen: Push and Rotate: a Complete Multi-agent Pathfinding Algorithm. J. Artif. Intell. Res. 51: pp. 443-492, 2014.
  3. Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner: The increasing cost tree search for optimal multi-agent pathfinding. Artif. Intell. 195, pp. 470-495, 2013.
  4. Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski: Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective. Proceedings of ECAI, pp. 810-818, 2016.


Poslední změna: 26.4.2019, 15:21