Implementation of M. Campbell's MILP Models for Multi-Robot Non-Adversarial Search paper.
Important Note: No parts of the code were borrowed or used from the author's implementation whatsoever. The entire project has been built from scratch with references duly credited in the Appendix.
You can read about the technical details underlying my implementation in my presentation. I have expanded more on the intuition in my blog post here.
Searchers(green) and target(red) just before capture
Capture event(pink)
- Obtain Gurobi license. There is a free academic license which is sufficient for our needs.
- Install Gurobi(for Linux)
git clone https://github.com/trunc8/multirobot-efficient-search-path-planning.gitcd multirobot-efficient-search-path-planningpip install -r requirements.txtpython3 code/main.py
You can find the results in the results directory
- Node labels in igraph
- Plotting as grid graph and saving
- Generating lattice graph
- Lots of stuff from here
- Multi-dimensional numpy decision variable
- Suppress gurobi optimizer output
- Finding neigborhood
- Adding title to igraph
- Adding multiple subgraphs to igraph
- Copy an igraph
- Understanding MIP
- When is update model required
- LinExp Error on applying quicksum to matrix variables
iGraph is best suited for our purpose based on this Reddit discussion
Use NetworkX for smaller networks and dynamic networks. NetworkX is pure Python, well documented and handles changes to the network gracefully.
iGraph is more performant in terms of speed and ram usage but less flexible for dynamic networks. iGraph is a C library with very smart indexing and storage approaches so you can load pretty large graphs in ram. The index needs to be updated whenever the graph changes, so dynamic graphs incur a lot of overhead.
Linear programming is P while integer programming is NP-hard.
- Siddharth Saha - trunc8
Created with ❤️ by Siddharth