Final report guidelines
|Here are some guidelines for the final project (remember, it is 30% of your grade).|
Please pick a paper / topic that you did not present
(1) Summarize the paper in your own words - This is supposed to be in high level but *use your own words*. Assume the reader is knoledgable in CS and AI and know the definition of MAPF and nothing more. The summary should be as sewlf-contained as possible. As a rule of thumb,a one-page summary suffacies.
(2) Following the summary, try and pinpoint what are the key takeaways and insights and note on any missing details or interesting extensions. This should be a couple of paragraphs long but shows the difference between repeatng the paper's some "deeper understanding"
(3) Design in detail a project around the paper. This should be roughly one page long snd should include the following points
(-) What are the outcomes (implement the approach is not a very good project)?
(-) What are the expected results?
(-) What tools are required to implement the project? If you are aware of open source implementations that could be used to start working on the project that would be great. You can check out in mapf.info if something exists.
As a sanity check, ask yourself if you would be excited to do this project (is it feasible? challenging? interesting? Is it clear what needs to be done and how?)
Each part will be given 10 points out of the total 30 points the project accounts toward your final grade.
|פורסם ב- 9/5/2022, 17:19:33 Created on 9/5/2022, 17:19:33 Создано 9/5/2022, 17:19:33 تم النشر ب- 9/5/2022, 17:19:33|
Grades for CBS project uploaded
I uploaded the grades for the CBS project.
In general they were great and I was happy to see a lot of 100s.
The grades were distributed 50% for the pdf and 50% for the wet part.
For the wet part, one point was given for each benchmark that got the desied result within a reasonable time budget (the fastest submission ran for less than a minute on my laptop so I gave everoe 15 mintes).
|פורסם ב- 9/5/2022, 17:18:00 Created on 9/5/2022, 17:18:00 Создано 9/5/2022, 17:18:00 تم النشر ب- 9/5/2022, 17:18:00|
Missing data from project reports
I checked the projects today (all in all - great job!).
Before publishing grades I wanted to clear some possible confusions.
(1) I had one submission containing only code and no report.
(2) I had four other submissions that did not contain answers to sec 2.5. In the instructions it was defined as "optional" but I explicity asked that you answer it. I assume that those thit did not made an honest mistake and wanted to give you a chance to resubmit this part (it is not a lot of work).
If you fall under one of the above catagories, please submit a revised report by the end of Thursday (5.5) end of day.
|פורסם ב- 2/5/2022, 20:06:51 Created on 2/5/2022, 20:06:51 Создано 2/5/2022, 20:06:51 تم النشر ب- 2/5/2022, 20:06:51|
Missing file from instances for CBS project
In Sec 3 of the handout it states that you should use exp3_1.txt.
There is no such file but you can test your code on any instance where the agents collide if they take their shortest path.
|פורסם ב- 28/3/2022, 14:58:44 Created on 28/3/2022, 14:58:44 Создано 28/3/2022, 14:58:44 تم النشر ب- 28/3/2022, 14:58:44|
MAPF-related talk at the Computational-Robotics Lab (CRL)
As mentioned in class, we will have a talk this Wednesday on MAPF as part of the CRL's weekly meetings.
You are more than welcome to attend (details are below).
The meeting will be in person at the CRL (first floor, next to the elavators).
p.s., next week's seminar is also going to be virtual.
Speaker Name: Tzivka Geft
Tzvika is a Ph.D. student at the Computational Geometry Lab, led by Dan Halperin, at Tel Aviv University, where he also completed his M.Sc. degree. Prior to that he obtained a B.Sc. degree in Computer Science at Tel Aviv University. Tzvika is interested in confronting NP-hard motion planning problems by improving the understanding of what makes such problems hard.
Distance-Optimal Multi-Agent Path Finding: New Hardness and Positive Results
Abstract: In Multi-Robot Motion Planning (MRMP) we aim to plan collision-free motion of robots from given start to target positions. Multi-Agent Path Finding (MAPF) is a discretized version of MRMP, where the robots are agents moving on a graph. In this two-part talk we will focus on the Distance-Optimal variant (DO-MAPF), in which the goal is to minimize the total distance traveled by the agents.
Part I: DO-MAPF is known to be hard for planar graphs. However, the input graph is commonly further restricted be a 2D grid, since grids can model well-structured environments, such as warehouses. Following this gap, Banfi et al. (2017) posed the tractability on 2D grids as an open question. We settle it by showing that this case remains NP-hard. Our reduction uses simple gadgets and is the first linear one for the planar case. The latter results in an exponential lower bound for the problem's running time, assuming the Exponential Time Hypothesis.
If time permits, I will also present related hardness results for quite restricted MRMP problem variants that are tractability frontiers, i.e., variants that are slight deviations from known tractable problems.
Part II: Inspired by intuition from the hardness proof, we devised an efficient heuristic algorithm for DO-MAPF. Our main innovation is a global outlook-based method of dynamic prioritization and adaptive paths. We keep the computational burden low by only using single-agent path queries. Experiments show that the algorithm quickly finds solutions better than 1.05-optimal for grids that have up to 25% of their vertices occupied by agents.
This talk is based on joint works with Yonatan Nakar (Part I), Noam Geller, Michael Bilevich (Part II) and Dan Halperin (both parts).
|פורסם ב- 27/3/2022, 16:09:49 Created on 27/3/2022, 16:09:49 Создано 27/3/2022, 16:09:49 تم النشر ب- 27/3/2022, 16:09:49|
Thanks for attending the first lecture today.
I had the rwong links and pdf on the website (sorry).
Now the new pdf of the first lecture is available undre "course material" as well as the link to the spreadsheet and the zoom link we will use for next two weeks.
|פורסם ב- 20/3/2022, 14:19:37 Created on 20/3/2022, 14:19:37 Создано 20/3/2022, 14:19:37 تم النشر ب- 20/3/2022, 14:19:37|
Hybrid lesson tomorrow
Tomorrow we will start the seminar in hybrid format using the following zoom link:
I know there are some students with COVID that cannot attend but I urge everyone who can to attend the class in person.
|פורסם ב- 19/3/2022, 19:55:07 Created on 19/3/2022, 19:55:07 Создано 19/3/2022, 19:55:07 تم النشر ب- 19/3/2022, 19:55:07|
Recording of seminar
|For those of you that missed the seminar and want to see it (I got at least one request).|
A recording can be found in the following link:
|פורסם ב- 8/3/2022, 15:18:58 Created on 8/3/2022, 15:18:58 Создано 8/3/2022, 15:18:58 تم النشر ب- 8/3/2022, 15:18:58|
MAPF-related seminar tomorrow (!), 4/6
|Hi guys and welcome to the robotics seminar!|
On Monday 4/6 (i.e., tomorrow), there is a seminar talk given by Nitzan Madar on a novel variant of the problem we will study this semester.
I highly recommend that you attend the talk. It will give you insight into what we will be studying this semester.
The talk will be at 9:30 using the following zoom link: https://technion.zoom.us/j/6269337580 and the abstract is below.
Looking forward to seeing you soon,
In Lifelong Multi-Agent Path Finding (L-MAPF) a team of agents performs a stream of tasks consisting of multiple locations to be visited by the agents on a shared graph while avoiding collisions with one another. L-MAPF is typically tackled by partitioning it into multiple consecutive, and hence similar, ``one-shot'' MAPF queries with a single task assigned to each agent, as in the Rolling-Horizon Collision Resolution (RHCR) algorithm. Therefore, a solution to one query informs the next query, which leads to similarity with respect to the agents' start and goal positions, and how collisions between the agents need to be resolved from one query to the next. Thus, experience from solving one MAPF query can potentially be used to speedup solving the next one and reduce runtime in L-MAPF overall. Despite this intuition, current L-MAPF planners solve consecutive MAPF queries from scratch. In this paper, we introduce a new RHCR-inspired approach called exRHCR, which exploits experience in its constituent MAPF queries. In particular, exRHCR employs a new extension of Priority-Based Search (PBS), a state-of-the-art MAPF solver. Our extension, called exPBS, allows to warm-start the search with the priorities between agents used by PBS in the previous MAPF instances. We demonstrate empirically that exRHCR solves L-MAPF up to 25% faster than RHCR, and allows to increase throughput for given task streams by as much as 3%-16% by increasing the number of agents we can cope with for a given time budget.
|עדכון אחרון ב- 6/3/2022, 13:05:18 Last updated on 6/3/2022, 13:05:18 Последняя модификация 6/3/2022, 13:05:18 تمت الحتلنة الأخيرة ب- 6/3/2022, 13:05:18|