{"id":110,"date":"2025-12-11T08:48:40","date_gmt":"2025-12-11T08:48:40","guid":{"rendered":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/?page_id=110"},"modified":"2026-04-30T08:16:38","modified_gmt":"2026-04-30T08:16:38","slug":"pf-r","status":"publish","type":"page","link":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/teaching\/pf-r\/","title":{"rendered":"Pathfinding and routing"},"content":{"rendered":"\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n<nav class=\"is-responsive wp-block-navigation is-layout-flex wp-block-navigation-is-layout-flex\" aria-label=\"Navigation\" \n\t\t data-wp-interactive=\"core\/navigation\" data-wp-context='{\"overlayOpenedBy\":{\"click\":false,\"hover\":false,\"focus\":false},\"type\":\"overlay\",\"roleAttribute\":\"\",\"ariaLabel\":\"Menu\"}'><button aria-haspopup=\"dialog\" aria-label=\"Open menu\" class=\"wp-block-navigation__responsive-container-open\" \n\t\t\t\tdata-wp-on-async--click=\"actions.openMenuOnClick\"\n\t\t\t\tdata-wp-on--keydown=\"actions.handleMenuKeydown\"\n\t\t\t><svg width=\"24\" height=\"24\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" viewBox=\"0 0 24 24\" aria-hidden=\"true\" focusable=\"false\"><rect x=\"4\" y=\"7.5\" width=\"16\" height=\"1.5\" \/><rect x=\"4\" y=\"15\" width=\"16\" height=\"1.5\" \/><\/svg><\/button>\n\t\t\t\t<div class=\"wp-block-navigation__responsive-container\"  id=\"modal-1\" \n\t\t\t\tdata-wp-class--has-modal-open=\"state.isMenuOpen\"\n\t\t\t\tdata-wp-class--is-menu-open=\"state.isMenuOpen\"\n\t\t\t\tdata-wp-watch=\"callbacks.initMenu\"\n\t\t\t\tdata-wp-on--keydown=\"actions.handleMenuKeydown\"\n\t\t\t\tdata-wp-on-async--focusout=\"actions.handleMenuFocusout\"\n\t\t\t\ttabindex=\"-1\"\n\t\t\t>\n\t\t\t\t\t<div class=\"wp-block-navigation__responsive-close\" tabindex=\"-1\">\n\t\t\t\t\t\t<div class=\"wp-block-navigation__responsive-dialog\" \n\t\t\t\tdata-wp-bind--aria-modal=\"state.ariaModal\"\n\t\t\t\tdata-wp-bind--aria-label=\"state.ariaLabel\"\n\t\t\t\tdata-wp-bind--role=\"state.roleAttribute\"\n\t\t\t>\n\t\t\t\t\t\t\t<button aria-label=\"Close menu\" class=\"wp-block-navigation__responsive-container-close\" \n\t\t\t\tdata-wp-on-async--click=\"actions.closeMenuOnClick\"\n\t\t\t><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" viewBox=\"0 0 24 24\" width=\"24\" height=\"24\" aria-hidden=\"true\" focusable=\"false\"><path d=\"m13.06 12 6.47-6.47-1.06-1.06L12 10.94 5.53 4.47 4.47 5.53 10.94 12l-6.47 6.47 1.06 1.06L12 13.06l6.47 6.47 1.06-1.06L13.06 12Z\"><\/path><\/svg><\/button>\n\t\t\t\t\t\t\t<div class=\"wp-block-navigation__responsive-container-content\" \n\t\t\t\tdata-wp-watch=\"callbacks.focusFirstElement\"\n\t\t\t id=\"modal-1-content\">\n\t\t\t\t\t\t\t\t<ul class=\"wp-block-navigation__container is-responsive wp-block-navigation\"><li class=\" wp-block-navigation-item wp-block-navigation-link\"><a class=\"wp-block-navigation-item__content\"  href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/\"><span class=\"wp-block-navigation-item__label\">Home<\/span><\/a><\/li><li class=\" wp-block-navigation-item wp-block-navigation-link\"><a class=\"wp-block-navigation-item__content\"  href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/teaching\/\"><span class=\"wp-block-navigation-item__label\">Teaching<\/span><\/a><\/li><li class=\" wp-block-navigation-item wp-block-navigation-link\"><a class=\"wp-block-navigation-item__content\"  href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/publications\/\"><span class=\"wp-block-navigation-item__label\">Publications<\/span><\/a><\/li><li class=\" wp-block-navigation-item wp-block-navigation-link\"><a class=\"wp-block-navigation-item__content\"  href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/thesis_topics\/\"><span class=\"wp-block-navigation-item__label\">Thesis topics<\/span><\/a><\/li><\/ul>\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div><\/nav>\n\n\n<hr class=\"wp-block-separator alignwide has-alpha-channel-opacity\"\/>\n\n\n\n<div class=\"wp-block-columns alignwide is-layout-flex wp-container-core-columns-is-layout-28f84493 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<p class=\"has-x-large-font-size\"><strong><a href=\"https:\/\/is.cuni.cz\/studium\/predmety\/index.php?id=b19035771213b21f864153438289383e&amp;tid=&amp;do=predmet&amp;kod=NAIL137&amp;skr=2025&amp;fak=11320\" data-type=\"link\" data-id=\"https:\/\/is.cuni.cz\/studium\/predmety\/index.php?id=b19035771213b21f864153438289383e&amp;tid=&amp;do=predmet&amp;kod=NAIL137&amp;skr=2025&amp;fak=11320\">Pathfinding and routing<\/a><\/strong><\/p>\n\n\n\n<p>This is an elective course that covers the basic concepts and methods of multi-agent pathfinding, as well as its practical applications. The course assumes basic knowledge of logic and search algorithms at the undergraduate level. The course aims to give students an overview of fundamental methods and concepts of multi-agent pathfinding, familiarize them with their practical usage, and present the current open problems in the research community (which are perfect topics for bachelor&#8217;s\/master&#8217;s theses).<\/p>\n\n\n\n<p><strong>Organization<\/strong><\/p>\n\n\n\n<p>The dates and times of the lecture will be determined based on the agreement with the students. The lecture will most likely be held in the corridor on the second floor of the Malostransk\u00e9 n\u00e1m\u011bst\u00ed building (rooms starting with S).<\/p>\n\n\n\n<p>To pass the course, the student must pass an exam. The exam is oral, with time for written preparation. The requirements correspond to the syllabus to the extent presented during the lectures.<\/p>\n\n\n\n<p><strong>Useful links and literature<\/strong> <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Webs\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/mapf.info\/\">MAPF community webpage<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/movingai.com\/benchmarks\/mapf\/index.html\">Benchmark set<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/www.leagueofrobotrunners.org\/\">League of robot runners competition<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/d3qvx1ggyg4lu1.cloudfront.net\/challenges\/flatland-challenge\">Flatland challenge<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Papers\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/arxiv.org\/pdf\/1906.08291\">Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/ieeexplore.ieee.org\/stamp\/stamp.jsp?tp=&amp;arnumber=10506521\">A Comprehensive Review on Leveraging Machine Learning for Multi-Agent Path Finding<\/a><\/li>\n\n\n\n<li>42+ Flavors of Multi-Agent Path Finding<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Repositories and implementation\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/github.com\/Jiaoyang-Li\/CBSH2-RTC\">CBS with many improvements<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/svancaj\/MAPF-encodings\">My SAT-based solver<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/Jiaoyang-Li\/MAPF-LNS2\">MAPF-LNS2<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/kei18\/lacam0\">LaCAM<\/a>, <a href=\"https:\/\/github.com\/kei18\/lacam3\">LaCAM3<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/Kei18\/mapf-visualizer\">Solution visualizer<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Lectures<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td>26.3.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/01MAPF_intro.pdf\">slides<\/a><\/td><td>Introduction, overview of topics to be discussed during the class<\/td><\/tr><tr><td>5.3.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/02MAPF_opt_solvers.pdf\">slides<\/a><\/td><td>Definitions, single agent pathfinding (A*, SIPP), CBS, Reduction to SAT, BCP<\/td><\/tr><tr><td>12.3.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/03MAPF_subopt_solvers.pdf\">slides<\/a><\/td><td>Sub-optimal solvers<\/td><\/tr><tr><td>19.3.<\/td><td><a href=\"https:\/\/www.youtube.com\/watch?v=XeZTyUS8ZF0\">video<\/a><\/td><td>PIBT, LaCAM and current research by Keisuke Okumura<\/td><\/tr><tr><td>26.3.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/04MAPF_ML.pdf\">slides<\/a><\/td><td>Decentralized solvers and ML in MAPF<\/td><\/tr><tr><td>2.4.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/05MAPF_Flavors.pdf\">slides<\/a><\/td><td>MAPF variants<\/td><\/tr><tr><td>9.4.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/06MAPF_Robots.pdf\">slides<\/a><\/td><td>MAPF on robots and safe execution policies<\/td><\/tr><tr><td>16.4.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/07MAPF_Cars.pdf\">slides<\/a><\/td><td>Autonomous cars and intersection management<\/td><\/tr><tr><td>23.4.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/08MAPF_Games.pdf\">slides<\/a><\/td><td>Games<\/td><\/tr><tr><td>30.4.<\/td><td><a href=\"https:\/\/ktiml.mff.cuni.cz\/~svancara\/files\/09MAPF_Routing.pdf\">slides<\/a><\/td><td>Routing problem<\/td><\/tr><tr><td>7.5.<\/td><td><\/td><td>Cancelled<\/td><\/tr><tr><td>14.5.<\/td><td>slides<\/td><td>Demos, videos, and open problems<\/td><\/tr><tr><td>21.5.<\/td><td><\/td><td>Exam<\/td><\/tr><\/tbody><\/table><\/figure>\n<\/div>\n<\/div>\n\n\n\n<div style=\"height:50px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Pathfinding and routing This is an elective course that covers the basic concepts and methods of multi-agent pathfinding, as well as its practical applications. The course assumes basic knowledge of logic and search algorithms at the undergraduate level. The course aims to give students an overview of fundamental methods and concepts of multi-agent pathfinding, familiarize [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":16,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-110","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/pages\/110","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/comments?post=110"}],"version-history":[{"count":21,"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/pages\/110\/revisions"}],"predecessor-version":[{"id":190,"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/pages\/110\/revisions\/190"}],"up":[{"embeddable":true,"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/pages\/16"}],"wp:attachment":[{"href":"https:\/\/ktiml.mff.cuni.cz\/~svancara\/wp-json\/wp\/v2\/media?parent=110"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}