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.
Robotics
Finally I am doing what I always want to do: the robots! This came after I finished my professorship in artificial intelligence. But better late than never. Still my robotics efforts
are connected with my research in AI which is focused on coordination of large groups of mobile robots in its abstract form known as multi-agent path finding (MAPF). Mobile robots are nice
but move only in 2D or 3D space. Why not to go into higher dimmensions: at least 6 or more?
And here we are, I need more complex robots, like octopus robots (Sentinels) seen in the Matrix movie.
But lets start with something more realistic, less evil, and more useful: 6+ degrees of freedom robotic arms.
This section just informs I am doing some robotics and it is not always up to date. Please see my Github profile for the most recent updates.
This is the new revision of the RR1 robotic arm (see below for the original robot) called revision 2 or rev.2 in short.
During the construction and operation of rev.1, I gained a lot of engineering experience, which I reflected in rev.2, which has many
improvements compared to rev.1. It can be said that rev.2 represents a very thorough redesign. I did improve everything I found not satisafactory in
the previous robot. Again, I follow the mindset that I do not improve individual parts too much separately, but rather within the entire robot, i.e. I always
build a complete robot with new parts and test it as a whole. A physical copy of rev.2 already exists as the photos below show.
It is important to note that the robot is open source (both hardware and software), which I am trying to fulfill even more with rev.2,
so everything I have created in connection with the robot is made freely available to the builder community, including
the source CAD files (sources for rev.1 was not published, only the STL files, because I never managed to get the source files in shape,
but for rev.2 I tried to keep the source files nicer, so I decided to publish them).
Here is a summary of the most important improvements that RR1 rev.2 brings:
(1) The encoders for the individual joints are no longer on the shafts of the stepper motors,
but directly on the joints, from which the torque is transmitted to the encoder by a belt (the GT2 6mm standard is used).
From this change, we expect better sensitivity and the eventual possibility to compensate for the deflection within the arm.
This change meant probably the biggest redesign, especially for the base turret, it was a challenge. But the overall design
based on aluminum extrusions helped a lot, on which the encoder can be fixed and the belt can be easily tensioned by changing
the position on the extrusion.
(2) Polycarbonate with carbon fiber is used instead of PETG for planetary gears and ring gears (the dark grey parts on the joints and everything inside is made of polycarbonate with carbon fiber).
In rev.1 it was shown that PETG gears can deform or even break after intensive operation with loads (as I show in the video here).
Polycarbonate with carbon fiber proved to be much better, it is a hard material, it feels like a stone, and also greatly reduced the backlash in the planetary gearboxes.
(3) Rev.2 uses the same type of split ring planetary gearboxes as rev.1, but they have larger ring gear diameters compared
to rev.1, which greatly improves torque. New gears has larger teeth that mesh together better. Additional bearings are also used to improve the stability of the joints.
The reduction ratio for large gearbox in the shoulder joint is approximately 1:40 which together with big Nema 23 motor (112mm in length) provides
enough torque to lift the arm.
(4) The overall kinematic aspect was changed for RR1 rev.2. The arm has a base turret shifted a little forward, which improves the working
space of the robot. The elbow link is further away from the elbow joint, which again improves the robot's dexterity
and its working space. But mainly thanks to this, the robot can be folded into a compact form which makes it possible to put the robot
in a standard large suitcase.
(5) The wrist has been completely redesigned, specifically the gripper is now attached both to the gearbox and also to
another additional bearing that surrounds the motor of the gripper. This design greatly reduced the deflection of the
gripper. The gripper itself has been redesigned. Compared to the rigid jaws in rev.1, rev.2 has jaws consisting of two
links, which allows for a more natural grasp of the object. In addition, the gripper in rev.2 has small anti-slip pads
on its surface, which enables smooth objects to be grasped.
Overall, it can be said that the RR1 rev. 2 is firmer and more rigid than rev. 1, which is certainly an advantage,
but the weight has also increased, quite significantly to 16.8kg (compared to approx. 14kg for rev.1), but it still
allows the robot to be transported in a larger suitcase. The increase in weight is mainly due to the extra bearings.
The other heavy parts, i.e. the stepper motors, remained the same.
Additional materials such as videos from tests and measurements are in preparation...
RR1 is a DIY desktop robotic arm, my first big project in robotics (not counting robotic projects when I was a child). The overall design
follows the idea of being able to produce more of these robots so that multi-robot coordination on the desktop is possible. Having a small scale Industry 4.0 on the table could
be great. The robot is bigger and more capable than toys but it is not too big like industrial robots. Thanks to its small size RR1 is not dangerous like industrial robots that need to be enclosed in
an inaccessible area. RR1 can be used as a collaborative robot.
RR1 has 6 (6 joints + 1 for the gripper) degrees of freedom and is powered by stepper motors. It is fully closed-loop,
i.e. every joint has its own encoder and at any time we know the current angles of all joints. The important feature that
distinguishes RR1 from other similar projects is that each joint has its own custom-built 3D-printed planetary gear reducer.
The robot consists of two parts: (i) the RR1 arm itself and (ii) a control computer called Real Box One, or RB1 in short. This allows for
having lot of electronics separated from the arm and supports modular design.
The first prototype, called "revision 1" is already running. The second prototype "rev. 2" is on the way (you can try to guess its color). As I gained huge experience during the assembly of "rev. 1", the second prototype "rev. 2" will
be much improved in many aspects.
RR1 specifications
Mass:
14kg (arm) + 8kg (control box)
Reach:
approx. 80cm
Repeatability:
still improving
Payload:
2kg
Material:
PETG, aluminum extrusions, metal bearings
Actuators:
Nema 23 and Nema 17 stepper motors
Reducers:
3D printed custom planetary gear reducers
Electronics:
Arduino Due
Stepper drivers:
7x DM556
A very distinguishing part of RR1 - my own design of a 3D-printable planetary gear reducer (in this case for the main lower joint with the reduction ratio 1:50) consisting of 3 planets - herringbone gears - and one middle gear connected to the motor axle.
Herringbone gears ensure smooth rolling of the entire mechanism with no clicking. The rotating part that moves the arm is fixed using bearing balls into the groove in the front orange part (balls and bolts are not shown,
there are also 7 small bearings that hold the gears). I am able to asseble the reducer so that it has almost no backlash!
Concepts come out of nowhere in my case. But then I have to make some effort to transform the concept into reality.
This shows few steps (with very big gaps between them): scetches, some CAD, and the first prototype of the RR1 robot.
Here are some videos from first tests of RR1 and its programming. To see more and up-to-date videos I recommend to subscribe to my Youtube channel.
The robot is completely open source (both hardware and software). Publishing of the material is little behind the actual development but at least some
files for the "rev.2" are available. All up-to-date material concerning the RR1 project will be published in the Github repository: https://github.com/surynek/RR1.
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 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.
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.
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.
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.
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.
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
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
Algorithms and Techniques of Knowledge Engineering: from theory to practical applications (Algoritmy a techniky znalostního inženýrství: od teorie k praktickým aplikacím)
Role: Principal investigator
Type: ČVUT Students Grant Project
Providers: Czech Technical University (ČVUT)
Period: 2023 - 2025
Contract number: SGS23/210/OHK3/3T/18
logicMOVE: Logic Reasoning in Motion Planning for Multiple Robotic Agents (Logické uvažování v plánování pohybu pro mnoho robotických agentů)
Role: Principal investigator
Type: Standard Research Project
Providers: Czech Science Foundation (Grantová agentura České republiky - GAČR)
Period: 2022 - 2024
Contract number: 22-31346S
Modern Algorithms and Techniques of Knowledge Engineering (Moderní algoritmy a techniky znalostního inženýrství)
Role: Principal investigator
Type: ČVUT Students Grant Project
Providers: Czech Technical University (ČVUT)
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 (Grantová agentura České republiky - GAČR)
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 (ČVUT)
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
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.
