Planning

We focus on the fundamental and applied research of planning problems in robotics and artificial intelligence. We consider limitations resulting from the practical deployment of robots - inaccurate navigation, noisy sensors, physical dimensions of robots, and their movement in a congested continuous workspace. The addressed tasks assume planning for a single robot as well as coordination of large fleets consisting of tens or hundreds of robots operating in known, partially known, or completely unknown environments. Contrary to classical approaches, which look for an optimal solution in an unlimited time, we develop methods generating high-quality results in a strictly limited time. Our solutions are based on a combination of approaches and knowledge from different scientific disciplines: artificial intelligence, computational geometry, graph theory, operational research, and of course, robotics. The research is split into two streams: routing problems and multi-agent path finding.

Routing Problems

Routing problems are one of the most studied classes of combinatorial optimization problems. We focus on the following variants of them:

The Travelling Deliveryman Problem (Minimum Latency Problem) – we develop approaches based on various metaheuristics for settings when computational time is strongly limited.
Generalized Travelling Salesman Problem over a set of maneuvers – we adapt metaheuristics for planning with specifically constrained trajectory segments
Travelling Salesman Problem with Neighborhoods, Close Enough Travelling Salesman Problem – we study variants of the Travelling Salesman Problem where cities to be visited are continuous sets in a plane.
Watchman Route Problem – we go towards a coupled solution to the problem of finding the shortest route from which a mobile robot can visually inspect a known 2D environment.
'Electric Vehicle Routing Problem – we won EVRP 2020 competition related to the VRP that considers limited cargo capacity and battery capacity of vehicles.
Mobile Robot Search and Exploration – we apply solutions to static routing problems for online planning in unknown environments

Publications

Woller, D., and Kulich, M. (2022). Path planning algorithm ensuring accurate localization of radiation sources. Applied Intelligence, 1–23 PDF URL BibTeX

@article{Woller22apin,
  author = {Woller, David and Kulich, Miroslav},
  doi = {10.1007/S10489-021-02941-Y},
  issn = {15737497},
  journal = {Applied Intelligence},
  keywords = {Combinatorial optimization,Generalized Large Neighborhood Search,Generalized Travelling Salesman Problem,Heuristics,Metaheuristics,Search for radiation sources},
  month = jan,
  pages = {1-23},
  publisher = {Springer},
  title = {Path planning algorithm ensuring accurate localization of radiation sources},
  url = {https://link.springer.com/article/10.1007/s10489-021-02941-y},
  year = {2022},
  access = {???},
  month_numeric = {1}
}

Mikula, J., and Kulich, M. (2022). Towards a continuous solution of the d-visibility watchman route problem in a polygon with holes. IEEE Robotics and Automation Letters, 7(3), 5934–5941. PDF URL BibTeX

@article{Mikula22ral,
  author = {Mikula, Jan and Kulich, Miroslav},
  journal = {IEEE Robotics and Automation Letters},
  title = {Towards a continuous solution of the d-visibility watchman route problem in a polygon with holes},
  year = {2022},
  volume = {7},
  number = {3},
  pages = {5934-5941},
  doi = {10.1109/LRA.2022.3159824},
  url = {https://ieeexplore.ieee.org/document/9736678/},
  issn = {2377-3766},
  access = {IEEE}
}

Mikula, J., and Kulich, M. (2022). Solving the traveling delivery person problem with limited computational time. Central European Journal of Operations Research, 1–31 PDF URL BibTeX

@article{Mikula2022cejor,
  author = {Mikula, Jan and Kulich, Miroslav},
  doi = {10.1007/S10100-021-00793-Y},
  issn = {16139178},
  journal = {Central European Journal of Operations Research},
  keywords = {Metaheuristics,Minimum latency problem,Run-time distribution,Traveling delivery person problem,Variable neighborhood search},
  month = jan,
  pages = {1-31},
  publisher = {Springer Science and Business Media Deutschland GmbH},
  title = {Solving the traveling delivery person problem with limited computational time},
  url = {https://link.springer.com/article/10.1007/s10100-021-00793-y},
  year = {2022},
  access = {???},
  month_numeric = {1}
}

Kulich, M., and Přeučil, L. (2022). Multi-robot search for a stationary object placed in a known environment with a combination of GRASP and VND. International Transactions in Operational Research, 29(2), pp. 805-836. PDF URL BibTeX

@article{Kulich20itor,
  author = {Kulich, Miroslav and Přeučil, Libor},
  title = {Multi-robot search for a stationary object placed in a known environment with a combination of GRASP and VND},
  year = {2022},
  journal = {International Transactions in Operational Research},
  volume = {29},
  number = {2},
  pages = {805-836},
  month = apr,
  language = {English},
  url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12794},
  doi = {10.1111/itor.12794},
  access = {submitted}
}

Kulich, M., Kubalík, J., and Přeučil, L. (2019). An Integrated Approach to Goal Selection in Mobile Robot Exploration. Sensors, 19(6). PDF URL BibTeX

@article{Kulich19sensors,
  author = {Kulich, Miroslav and Kubalík, Jiří and Přeučil, Libor},
  title = {An Integrated Approach to Goal Selection in Mobile Robot Exploration},
  year = {2019},
  number = {6},
  journal = {Sensors},
  volume = {19},
  month = mar,
  language = {English},
  url = {https://www.mdpi.com/1424-8220/19/6/1400/htm},
  doi = {10.3390/s19061400},
  month_numeric = {3}
}

Kulich, M., Miranda Bront, J. J., and Přeučil, L. (2017). A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment. Computers & Operations Research, 84. PDF URL BibTeX

@article{Kulich17cor,
  author = {Kulich, Miroslav and Miranda Bront, Juan José and Přeučil, Libor},
  title = {A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment},
  year = {2017},
  journal = {Computers \& Operations Research},
  volume = {84},
  month = aug,
  language = {English},
  url = {http://www.sciencedirect.com/science/article/pii/S0305054816300995},
  doi = {10.1016/j.cor.2016.04.029},
  access = {accepted},
  month_numeric = {8}
}

Multi-Agent Path Finding

Assume a fleet of mobile agents moving on a discrete graph. Multi-Agent Path Finding (MAPF) stands for the problem of finding an optimal, collision-free trajectory for each agent from their start positions to given goal positions. We address the following subproblems:

Fast replanning - we study how to reuse the prior planning knowledge to speed up the replanning process.
Heterogeneous fleets – we assume various types of agents, e.g. high priority agents (humans), different speeds of agents, restricted areas for some agents, etc.
Multi-agent Multi-item Pickup and Delivery – we study problems where agents can carry more than one item at the same moment and thus solve task assignment and MAPF simultaneously.
Robust plan execution and repair - we develop techniques for detecting and classifying future issues during plan execution that are going beyond classical obstacle avoidance, for resolving execution failures, either offline by generating robust plans or online by re-scheduling and re-planning.

Publications

Rybecký, T., Kulich, M., Andreychuk, A., and Yakovlev, K. (2021). Towards Narrowing the Search in Bounded-Suboptimal Safe Interval Path Planning. Proceedings of the International Symposium on Combinatorial Search, 12(1), 136–140. PDF URL BibTeX

@inproceedings{Rybecky21socs,
  title = {Towards Narrowing the Search in Bounded-Suboptimal Safe Interval Path Planning},
  author = {Rybecký, Tomáš and Kulich, Miroslav and Andreychuk, Anton and Yakovlev, Konstantin},
  booktitle = {Proceedings of the International Symposium on Combinatorial Search},
  volume = {12},
  number = {1},
  pages = {136--140},
  year = {2021},
  publisher = {AAAI Press},
  isbn = {978-1-57735-870-1},
  access = {full}
}

Petković, T., Hvězda, J., Rybecký, T., Marković, I., Kulich, M., Přeučil, L., and Petrović, I. (2020). Human Intention Recognition for Human Aware Planning in Integrated Warehouse Systems. 28th Mediterranean Conference on Control and Automation (MED), 586–591. PDF URL BibTeX

@inproceedings{Petkovic20med,
  author = {Petković, Tomislav and Hvězda, Jakub and Rybecký, Tomáš and Marković, Ivan and Kulich, Miroslav and Přeučil, Libor and Petrović, Ivan},
  booktitle = {28th Mediterranean Conference on Control and Automation (MED)},
  title = {Human Intention Recognition for Human Aware Planning in Integrated Warehouse Systems},
  year = {2020},
  volume = {},
  number = {},
  pages = {586-591},
  publisher = {IEEE},
  doi = {10.1109/MED48518.2020.9183266},
  access = {IEEE}
}

Yakovlev, K., Andreychuk, A., Rybecký, T., and Kulich, M. (2020). On the Application of Safe-Interval Path Planning to a Variant of the Pickup and Delivery Problem. Proceedings of the 17th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,, 521–528. PDF URL BibTeX

@conference{Yakovlev20icinco,
  author = {Yakovlev, Konstantin and Andreychuk, Anton and Rybecký, Tomáš and Kulich, Miroslav},
  title = {On the Application of Safe-Interval Path Planning to a Variant of the Pickup and Delivery Problem},
  booktitle = {Proceedings of the 17th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
  year = {2020},
  pages = {521-528},
  publisher = {SciTePress},
  organization = {INSTICC},
  doi = {10.5220/0009888905210528},
  isbn = {978-989-758-442-8},
  access = {full}
}

Kulich, M., Novák, T., and Přeučil, L. (2019). Push, Stop, and Replan: An Application of Pebble Motion on Graphs to Planning in Automated Warehouses. 2019 IEEE Intelligent Transportation Systems Conference (ITSC). PDF URL BibTeX

@inproceedings{Kulich19itsc,
  author = {Kulich, Miroslav and Novák, Tomáš and Přeučil, Libor},
  title = {Push, Stop, and Replan: An Application of Pebble Motion on Graphs to Planning in Automated Warehouses},
  booktitle = {2019 IEEE Intelligent Transportation Systems Conference (ITSC)},
  publisher = {IEEE Xplore},
  address = {Auckland},
  year = {2019},
  language = {English},
  url = {https://ieeexplore.ieee.org/document/8916906},
  doi = {10.1109/ITSC.2019.8916906},
  access = {IEEE}
}

Hvězda, J., Rybecký, T., Kulich, M., and Přeučil, L. (2018). Context-Aware Route Planning for Automated Warehouses. Proceedings of 2018 21st International Conference on Intelligent Transportation Systems (ITSC). PDF URL BibTeX

@inproceedings{Hvezda18itsc,
  author = {Hvězda, Jakub and Rybecký, Tomáš and Kulich, Miroslav and Přeučil, Libor},
  title = {Context-Aware Route Planning for Automated Warehouses},
  booktitle = {Proceedings of 2018 21st International Conference on Intelligent Transportation Systems (ITSC)},
  publisher = {IEEE Intelligent Transportation Systems Society},
  address = {Maui},
  year = {2018},
  language = {English},
  doi = {10.1109/ITSC.2018.8569712},
  access = {IEEE}
}

Hvězda, J., Kulich, M., and Přeučil, L. (2018). Improved Discrete RRT for Coordinated Multi-robot Planning. Proceedings of the 15th International Conference on Informatics in Control, Automation and Robotics - (Volume 2). PDF URL BibTeX

@inproceedings{Hvezda18icinco,
  author = {Hvězda, Jakub and Kulich, Miroslav and Přeučil, Libor},
  title = {Improved Discrete RRT for Coordinated Multi-robot Planning},
  booktitle = {Proceedings of the 15th International Conference on Informatics in Control, Automation and Robotics - (Volume 2)},
  publisher = {SciTePress},
  address = {Madeira, PT},
  year = {2018},
  language = {English},
  url = {http://www.scitepress.org/PublicationsDetail.aspx?ID=ppwUqsGaX18=\&t=1},
  doi = {10.5220/0006865901710179},
  access = {full}
}

Contact: Miroslav Kulich

Page last modified on June 08, 2022, at 08:56 AM EST