My Research Profile

This is a general overview of what I am doing in computer science, what I have already achieved, or what I would like to do. There are still so many topics I would like to look more deeply inside. It is true that my talent is limited in many ways and my own research is just a tiny contribution to science, but research is what I extremely like to do. My dream is to taste all of the artificial intelligence topics at the research level - I have done something towards this goal already.

"I have no special talents I am only passionately curious." - Albert Einstein

Research Topics

  • Computer Graphics (1995 - 1998). My first research topic. I was fascinated with photo realistic rendering. Quickly I had my own C++ implementation of ray-tracing and a speacial 3D-modeling language. At that time, the calculation of a singe image showing a simple scene took hours (my 386 PC was still running overnight). What a progress we had, today GPU accelerated ray-tracing (RTX) can compute scenes in real-time (30+ fps). I participated with my programs in various student competitions.
  • Neural Networks (1999 - 2002). This topic reflected my growing interest in artificial intelligence. Made a software called Neural Network Laboratory (nn-lab) (available from my archival web page). Implemented the Backpropagation algorithm and some genetic learning stuff. Did lot of vector-like optimizations to compute weighted sums in Backpropagation quickly. Again we had a great progress. All I did, nowadays can be done on GPUs.
  • Constraint Programming (2002 - present). Worked on dynamic CSP where constraints are dynamicaly added and/or removed as part of my master thesis. Developed algorithms for maintaining dynamic arc-consistency (DnAC). Authored the AC|DC-2 algorithm and its improved version AD|DC-2i. My first publication comes from this - at the CP conference in 2004 (right after defending my master thesis; had no idea that CP is a higly ranked conference at that time).
  • Automated Planning (2004 - present). Started as my doctoral dissertation topic. I regard the topic as one of cores of artificial intellignce. Most ideas derived from the GraphPlan algorithm. Developed several techniques for more efficient extraction of plans from planning graphs. Ideas such as projection consistency or maintaining AC in GraphPlan comes from this research. Got some awards for the work including University Bolzano Foundation Award (= money; forgot how did I spend them).
  • Boolean Satisfiability (2006 - present). I was not satisfied with constraint programming technology at that time due to heterogeneity of constraints and not satisfactory performance of CPS solvers. The answer was Boolean Satisfiability (SAT) with its simple homogeneous language (CNF formulae) and fast solvers. I started to port my previous ideas from GraphPlan to SAT. The outcome of this research is a SAT preprocessing technique based on clique detection in graphs derived from input formulae. The technique can quickly solve the Pigeon Hole Principle problems faster than best SAT solvers of that time.
  • Multi-agent Path Finding (2008 - present). I started this topic during waiting for the defense of my dissertation. Quickly I had the BIBOX algorithm - my most cited work so far, an algorithm for finding feasible MAPF plans on bi-connected graphs in polynomial time. Other polynomial time algorithms for MAPF (like Push-and-Swap and Push-and-Rotate) came later after BIBOX. A bit later I started to work on optimal MAPF solving through compiling it to SAT. I have came up with many SAT encodings sice 2012 when I started this. Lot of work has been done jointly with my collaborators (Ariel Felner (BGU), Roni Stern (BGU), Sven Koenig (USC), Jiaoyang Li (USC), Adi Botea (IBM Research) (feeling that I forgot someone, I will fix the list later).
  • Heuristic Search/Games (2008 - present). With my students (most notably Petr Michalík) I did lot of work in 15-Puzzle and (N2-1)-Puzzle solving. We managed to outperform existing on-line algorithms through a so-called snake formation. The idea of snake formation eventually applied to MAPF as well. Many heuristic search-based algorithms have been developed for the ACPF - Adversarial version of MAPF (with Marika Ivanová). There are still many open questions in ACPF.
  • Computational Complexity (2008 - present). I have been dealing with computational complexity and boundaries of artificial intelligence all the time. I wrote some proofs on hardness/completeness of variants of MAPF problems - I like these proof techniques as they show interesting mechanical properties of the problem. Many complexity results for ACPF I made jointly with my students (most notably Marika Ivanová, to be honest she ivented majority of ideas for ACPF complexity proofs while I just said (usually wrongly) that this or that is a good or bad direction).
  • Motion Planning/Robotics (2008 - present). This was the most important motivation for MAPF that I originally started as a robotic problem. I consider motion understanding as a core problem in robotics. This research is on-going. I would like to address motion planning from the combinatorial and logic perspective. Well developed research in MAPF provides a good foundation to make reasonable generalizations towards motion planning.

International Collaboration

I have spent some at various instituions. Sometimes a fruitful collaboration resulted from my stays. Below is the list of institutions I have been involved with somehow.

Kobe University, Japan (artificial intelligence, robot navigation, distributed CSP), BGU - Ben Gurion University of the Negev, Israel (MAPF, heuristic search), USC - University of Southern California, USA (MAPF, robotics), Waseda University, Japan (graph theory), AIRC/AIST - Artificial Intelligence Resarch Center/National Institute of Advanced Industrial Science and Technology, Tokyo, Japan (robotics, artificial intelligence), NII - National Institute of Informatics, Tokyo, Japan, AIP/Riken, Tokyo, Japan, IBM Resarch, Ireland.

Industrial Collaboration

I also have true industrial experience at full-time positions like software analyst and software developer (train communication hardware/real-time programming, hardware verification). This hopefully gives me a better understanding of what are the needs of industrial research&development. Significant academy-industry collaboration I participated in include partners like Deloitte Touche Tohmatsu Limited and others.


Various research related software I have developed by myself or in collaboration with my colleagues is presented on this page. You can download the presented software and use it in your own research and experiments. Most programs are written in C++ and complete source code is provided. I hope you find them to be informative and helpful.

Github turned out to be the excelent tool to present most recent versions of my source codes. So I recently started to post some of my important programs through my Github profile.

reLOC : an experimental package for solving multi-agent path finding (MAPF) problems


reLOC is an experimental software for solving relocation problems. Most functions are dedicated to solving a special relocation problem known as multi-agent path finding (MAPF) where a number of distinguishable agents are relocated in a graph from their starting vertices to unique goal vertices while collisions between agents must be avoided. The reLOC package implements several SAT-based optimal methods (the MAPF instance is reduced to propositional satisfiability instance (SAT) and then solved by a SAT solver) including state-of-the-art MDD-SAT. SAT-based methods use the Glucose SAT solver. Two objective functions are implemented - makespan and sum-of-costs. Polynomial-time complete solving methods based on Push-and-Swap algorithm are implemented as well.

Source download


(released July 2017)



(released September 2018)

Recently we have added support for token relocation problems: token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). For token relocation please refer to newer versions of reLOC.

Please cite the following paper if you use the reLOC program in your own published research on MAPF:

Pavel Surynek: Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs. Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI 2014), pp. 875-882, Limassol, Cyprus, IEEE Press, 2014, ISBN 978-1-4799-6572-4.

If you use reLOC in a research dealing with token swapping then it is better to cite:

Pavel Surynek: Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT. Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI 2018), pp. 592-599, Volos, Greece, IEEE Press, 2018.

boOX : an experimental package for solving item relocation problems

boOX is another experimental software for solving item relocation problems. Development of boOX started after similar package reLOC hence boOX implements some more fresh ideas than reLOC. While most parts of reLOC concerns SAT-based MDD-SAT solver, boOX implements many versions of the standard conflict-based search (CBS) and also a new algorithm combining SAT-based problem solving and conflict-based search through satisfiability modulo theories (SMT) called SMT-CBS.

Currently the package supports solving multi-agent path finding (MAPF), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). All problems can be solver by the standard CBS and by SMT-CBS. The implementation of SMT-CBS algorithm is currently based on Glucose.

Source download


(released September 2018)


Please cite the following preprint if you use the boOX program in your own published research on item relocation:

Pavel Surynek: Lazy Modeling of Variants of Token Swapping Problem and Multi-agent Path Finding through Combination of Satisfiability Modulo Theories and Conflict-based Search. arXiv, CoRR abs/1809.05959, Cornel University Library, 2018.

boOX : Leibniz Edition

Recent developments in the boOX project were focused on the improvement of SMT-CBS which now represents state-of-the-art SMT-based algorithm for MAPF. SMT-CBS significantly outperforms the previos SAT-based MAPF solver MDD-SAT. The final implementation of SMT-CBS has been released as part of Zenon edition.

Zenon edition source: 


(released February 2019)

Major progress was also done on the SMT-based solver for the continuous version of MAPF where agents move smoothly in the continuous space and time (MAPFR). Preliminary version of the SMT-based solver for MAPFR is part of the Leibniz edition.

Leibniz edition source: 


(released May 2019)

Please cite the following preprint if you use the boOX project in a relation to MAPFR solving:

Pavel Surynek: Multi-agent Path Finding with Continuous Time Viewed Through Satisfiability Modulo Theories (SMT). arXiv, CoRR abs/1903.09820, Cornel University Library, 2019.

boOX : Planck Edition

This is a new version of the boOX project implementing among others solvers for multi-agent path finding with continuous time (MAPFR) and geometric agents. The new solver called SMT-CBSR is implemented for both common objectives in MAPFR: makespan and the sum-of-costs. SMT-CBSR is a SAT/SMT (satisfiability modulo theories) based solver running on top of the Glucose SAT solver.

Although SMT-CBSR bridges the gap between continuous MAPFR environment and the yes/no discrete world of SAT solvers, the implementation of the solver for the makespan objective was quite easy. Making it for the sum-of-costs objective was more challenging. We need to combine iterative strategy for increasing makespan known from the SATPlan planner for finding optimal plans with a sort of branch-and-bound technique to establish bound on numeric sum-of-costs through incremental cardinality constraints.

Planck edition source: 


(released April 2020)


Please cite the following preprint if you use the boOX project in a relation to MAPFR solving with various objectives:

Pavel Surynek: Pushing the Envelope: From Discrete to Continuous Movements in Multi-Agent Path Finding via Lazy Encodings.. arXiv, CoRR abs/2004.13477, Cornel University Library, 2020.

Programme Committee Membership

  • SoCS 2021: 14th Annual Symposium on Combinatorial Search
  • IJCAI 2021 (area chair): 30th International Joint Conference on Artificial Intelligence
  • AAAI 2021 (senior PC member): 35th AAAI Conference on Artificial Intelligence
  • SoCS 2020: 13th Annual Symposium on Combinatorial Search
  • ICTAI 2020: 32nd International Conference on Tools with Artificial Intelligence
  • WoMAPF 2020: 4th International Workshop on Multi-Agent Path Finding
  • IJCAI-PRICAI 2020 (senior PC member): 29th International Joint Conference on Artificial Intelligence /
        17th Pacific Rim International Conference on Artificial Intelligence
  • AAAI 2020: 35th AAAI Conference on Artificial Intelligence
  • AAMAS 2020 (external reviewer): 19th International Joint Conference on Autonomous Agents and Multiagent Systems

  • and more: AAMAS 2019, IJCAI 2019, ICTAI 2019, ICAPS 2019, AAAI 2019, ICTAI 2018, IJCAI-ECAI 2018, ICAPS 2018, ICAART 2018, AAAI 2018, SoCS 2017, AAAI 2017, IJCAI 2016, AAAI 2016, AAMAS 2015, ECAI 2014, AAMAS 2014, IJCAI 2013, AAAI 2011

Journal Article Reviewing

The list of journals I have made reviews for (year indicates when the review has been completed).

  • IEEE Access 2021
  • IEEE Transactions on Computers 2021 (TC 2021)
  • Journal of Artificial Intelligence Research 2020 (JAIR 2020)
  • IEEE Access 2020
  • Science Robotics 2020 (2020)
  • Computers, Environment and Urban Systems 2020 (CEUS 2020)
  • Robotics and Autonomous Systems 2020 (Robot 2020)
  • SAGE Open 2020
  • Journal of Artificial Intelligence Research 2019 (JAIR 2019)
  • IEEE Robotics and Automation Letters 2019 (RA-L 2019)
  • 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2019)
  • Constraints: An International Journal 2019
  • IEEE Robotics and Automation Letters 2018 (RA-L 2018)
  • IEEE Transactions on Computers 2018 (T-CO 2018)
  • Autonomous Robots 2017 (AURO 2017)
  • Artificial Intelligence Journal 2016 (AIJ 2016)
  • IEEE Transactions on Robotics 2015 (T-RO 2015)
  • IEEE Transactions on Automation Science and Engineering (T-ASE 2015)
  • IEEE International Conference on Automation Science and Engineering (CASE 2014)
  • Robotics and Autonomous Systems, Elsevier (Robot 2013)
  • IEEE Transactions on Robotics 2013 (T-RO 2013)
  • Robotics and Computer Integrated Manufacturing (RCIM 2013)
  • International Journal of Computer Mathematics (IJCM 2013)
  • 2013 IEEE International Conference on Robotics and Automation (ICRA 2013)
  • Theoretical Computer Science 2011 (TAMC 2010 Special Issue)
  • Principles and Practice of Constraint Programming (CP 2011)
  • Constraints: An International Journal 2010
  • Annual Conference on Theory and Applications of Models of Computation 2010 (TAMC 2010)
  • Constraints: An International Journal 2010
  • Journal Kybernetika 2008
  • International Joint Conference on Artificial Intelligence 2009 (IJCAI 2009)
  • Principles and Practice of Constraint Programming (CP 2007)
  • Recent Advances in Constraints 2007 (RAC 2007), CSCLP 2007 post-proceedings

Grant Projects

  • Modern Algorithms and Techniques of Knowledge Engineering (Moderní algoritmy a techniky znalostního inženýrství)
    Role: Principal investigator
    Type: CTU Students Grant Project
    Providers: Czech Technical University
    Period: 2020 - 2022
    Contract number: SGS20/213/OHK3/3T/18
  • intALG-MAPFg: Intelligent Algorithms for Generalized Variants of Multi-agent Pathfinding (Inteligentní algoritmy pro zobecněné varianty multi-agentního hledání cest)
    Role: Principal investigator
    Type: Standard Research Project
    Providers: Czech Science Foundation
    Period: 2019 - 2021
    Contract number: 19-17966S
  • Modern data-mining methods for advanced extraction of information from data (Moderní data-miningové metody pro pokrocilé vytežování informací z dat)
    Role: Principal investigator (jointly with Doc. RNDr. Ing. Marcel Jiřina, Ph.D.)
    Type: CTU Students Grant Project
    Providers: Czech Technical University
    Period: 2017 - 2019
    Contract number: SGS17/210/OHK3/3T/18
  • Integration of Heuristic Search and Compilation-based Techniques for Multi-agent Path-finding (Integrace heuristického prohledávání a kompilačních technik pro hledání cest s mnoha agenty)
    Role: Czech-side investigator
    Israeli side: Prof. Ariel Felner, Dr. Roni Stern (Ben Gurion University of the Negev)
    Type: Bilateral institutional cooperation
    Providers: Czech Ministry of Education Youth and Sports (Ministerstvo školství mládeže a tělovýchovy České republiky - MŠMT) and Israel Ministry of Science, Technology and Space
    Period: 2017 - 2018
    Contract number: 8G15027
  • Constraint Programming and Boolean Satisfiability for Artificial Intelligence (Omezující podmínky a booleovská splnitelnost pro umělou inteligenci)
    Role: principal investigator
    Type: Post-doctoral project
    Provider: Czech Science Foundation (Grantová agentura České republiky - GAČR)
    Period: 2009 - 2011
    Contract number: 201/09/P318
  • PlanEx: Bridging Planning and Execution
    Role: member
    Type: Standard research project
    Provider: Czech Science Foundation (Grantová agentura České republiky - GAČR)
    Period: 2010 - 2014
    Contract number: GAP103/10/1287
  • Dynamic Aspects of Scheduling (Dynamické aspekty rozvrhování)
    Role: member
    Type: Standard research project
    Provider: Czech Science Foundation (Grantová agentura České republiky - GAČR)
    Period: 2007 - 2009
    Contract number: 201/07/0205
  • Constraint Satisfaction in Planning (Omezující podmínky v plánování)
    Role: member
    Type: Doctoral project
    Provider: Grant Agency of Charles University (Grantová agentura Univerzity Karlovy)
    Period: 2006 - 2008
    Contract number: 356/2006/A-INF/MFF
  • Collegium Informaticum
    Role: member
    Type: Doctoral project
    Provider: Czech Science Foundation (Grantová agentura České republiky - GAČR)
    Period: 2005 - 2008
    Contract number: 201/07/0205


Co-Chair/Organizer of the 12th Annual Symposium on Combinatorial Search (SoCS 2019), California, USA, []
Session Chair at ICAART 2017, Porto, Portugal
- session Artificial Intelligence 1
Session Chair at SoCS 2015, Ein Gedi, Israel
- technical session and poster spotlight session
Faculty Open Day 2015, Prague Congress Center, Czechia
- representative of the department, together with Jakub Střelský
Faculty Open Day 2014, Slovanský dům, Prague, Czechia
- representative of the department, together with Tran Tuan Hiep
Faculty Open Day 2013, Slovanský dům, Prague, Czechia
- representative of the department, together with Marika Ivanová and Tran Tuan Hiep
Gaudeamus Fair 2012, Brno Exhibition Centre, Brno, Czechia
- education and study show, representative of the faculty
Faculty Open Day 2012, Slovanský dům, Prague, Czechia
- representative of the department
Session Chair at ICTAI 2011, Boca Raton, FL, USA
- session Planning I
Session Chair at AAAI 2011, San Francisco, CA, USA
- sessions A* Search and Search 2
Web Master of department web (2009-2016),
- Department of Theoretical Computer Science, Charles University, []
Web Master for Czech-Japan Seminar 2011 (CJS 2011),
Hejnice, Czechia, []

Selected Invited Talks

SAT-based Multi-Agent Path Finding,
IJCAI 2019 Workshop on Multi-Agent Path Finding, August 2019, Macau, China.

Cooperative Path-planning for Multiple Robots,
Ben Gurion University of the Negev, Advanced Topics in Artificial Intelligence, March 2015, Beer Sheva, Israel.

Artificial Intelligence and Computer Driven Society,
University of Hyogo, May 2012, Kobe, Japan.

Cooperative Path-finding as Satisfiability,
4th CSPSAT Seminar, May 2012, Kobe University, Japan.

Global Consistencies in Boolean Satisfiability,
2nd CSPSAT Seminar 2010, Information Science and Technology Center of the Kobe University, November 2010, Kobe University, Japan.

Path-planning for Multiple Robots,
2nd CSPSAT Seminar 2010, Information Science and Technology Center of the Kobe University, November 2010, Kobe University, Japan.