Research




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

Unlike some other 'theoretical computer scientists' I 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. Unfortunately, most of my industrial collaborations is secret. But let me name some significant partners at least: Good AI / Keen Software House a.s., Deloitte Touche Tohmatsu Limited, ...




Software

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   

reLOC is an experimental software for solving relocation problems. Most functions are dedicated to solving of 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). 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

reLOC-0.16-takao_013.tgz  

(released July 2017)

 

reLOC-0.20-kruh_043.tgz  

(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), 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 of 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

boOX-0_iskra-104.tgz  

(released September 2018)

   boOX   

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.




Programme Committee Membership

  • AAMAS 2019: 18th International Joint Conference on Autonomous Agents and Multiagent Systems
  • ICAPS 2019: 29th International Conference on Automated Planning and Scheduling
  • AAAI 2019: 34th AAAI Conference on Artificial Intelligence
  • ICTAI 2018: 30th International Conference on Tools with Artificial Intelligence
  • IJCAI-ECAI 2018: 27th International Joint Conference on Artificial Intelligence /
        23rd European Conference on Artificial Intelligence
  • ICAPS 2018: 28th International Conference on Automated Planning and Scheduling
  • ICAART 2018: 11th International Conference on Agents and Artificial Intelligence
  • AAAI 2018: 33rd AAAI Conference on Artificial Intelligence
  • SoCS 2017: 10th Annual Symposium on Combinatorial Search
  • AAAI 2017: 31st Conference on Artificial Intelligence
  • IJCAI 2016: 25th International Joint Conference on Artificial Intelligence
  • AAAI 2016: 30th Conference on Artificial Intelligence
  • AAMAS 2015: 14th International Joint Conference on Autonomous Agents and Multiagent Systems
  • ECAI 2014: 21st European Conference on Artificial Intelligence
  • AAMAS 2014: 13th International Joint Conference on Autonomous Agents and Multiagent Systems
  • IJCAI 2013: 23rd International Joint Conference on Artificial Intelligence
  • AAAI 2011: 25th Conference on Artificial Intelligence



Article Reviewing

  • 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

  • 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: GA-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



Service

Co-Chair/Organizer of the 12th Annual Symposium on Combinatorial Search (SoCS 2019), California, USA, [http://socs19.search-conference.org]
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, [http://ktiml.mff.cuni.cz]
Web Master for Czech-Japan Seminar 2011 (CJS 2011),
Hejnice, Czechia, [http://ktiml.mff.cuni.cz/cjs2011]



Invited Talks

Cooperative Path-planning for Multiple Robots,
An invited talk at the Ben Gurion University of the Negev, Advanced Topics in Artificial Intelligence, March 2015, Israel.
presentation pdf ]

Artificial Intelligence and Computer Driven Society,
An invited talk at the University of Hyogo, May 2012, Japan.
abstract pdf | poster pdf | presentation pdf ]

Cooperative Path-finding as Satisfiability,
A talk at the 4th CSPSAT Seminar, May 2012, Kobe University, Japan.
presentation pdf ]

Redundancy Elimination in Highly Parallel Solutions of Motion Coordination Problems,
A talk at the CSP Seminar at Graduate School of Maritime Sciences, October 2011, Kobe University, Japan.
presentation pdf ]

Global Consistencies in Boolean Satisfiability,
An invited talk at the 2nd CSPSAT Seminar 2010, Information Science and Technology Center of the Kobe University, November 2010, Kobe University, Japan.
presentation pdf ]

Path-planning for Multiple Robots,
An invited talk at the 2nd CSPSAT Seminar 2010, Information Science and Technology Center of the Kobe University, November 2010, Kobe University, Japan.
presentation pdf ]

Hodnocení výzkumu (On Research Evaluation),
A talk at the department meeting, September 2010, Slapy, Faculty of Mathematics and Physics, Charles University, Prague, Czechia.
presentation pdf ]

Centralized Multi-agent Path Planning,
An invited talk at the Seminar of Agent Technology Center, June 2010, Faculty of Electrical Engineering, Czech Technical University, Prague, Czechia.
presentation pdf ]

Path Planning for Multiple Robots,
A talk at the 18th Annual Student Conference Week of Doctoral Students 2009, June 2009, Faculty of Mathematics and Physics, Charles University, Prague, Czechia.
presentation pdf ]

Plánování cest pro mnoho robotů (Multi-robot path planning),
A talk at the Seminar on Artificial Intelligence, April 2009, Faculty of Mathematics and Physics, Charles University, Prague, Czechia.
presentation pdf ]