search

whoenig / libMultiRobotPlanning

Library with search algorithms for task and path planning for multi robot/agent systems
MIT License
814 stars 218 forks source link

Added script to convert standard benchmarks #10

Closed kylevedder closed 5 years ago

kylevedder commented 5 years ago

Added script to convert standard benchmarks, such as those found at https://movingai.com/benchmarks/mapf/index.html, and converts them into YAML files usable by the example/ implementations provided by this library.

whoenig commented 5 years ago

Very nice - thanks! Did you already run some tests on how this repository compares to other implementations (or algorithms)?

kylevedder commented 5 years ago

I've compared CBS against M (https://github.com/gswagner/mstar_public), Liron's implementation of AFS, and my planner, X, which is in a branch of my fork of your repo (https://github.com/kylevedder/libMultiRobotPlanning/tree/xstar). More info on X*, though ignore the experimentation as it's being re-done.

I've not done massive experimentation, but I have data for time to solutions for 100x100 grid with 5% random obstacles, 30 random trials per agent configuration, each with a 20 minute timeout.

This is a plot of time to first solution (both X and AFS are anytime, while M and CBS are optimal solvers, so a bit of skew in favor of AFS and X* should be expected) xstar_vs_all_first_times

Here's a plot of time to optimal solution; CBS is competitive with the rest of the algorithms xstar_vs_all_optimal_times

I'll have more robust experimentation in my journal paper, which I hope to be done with a draft of in a few weeks. I will let you know if I notice bugs or poor performance, but thus far all of your code has been rock solid.

whoenig commented 5 years ago

Thanks Kyle - this looks like super interesting research. Keep me posted if you find bugs/issues and also once your journal paper gets published!