Ongoing task lists

[gdalle]

Wednesday, Nov 15th

@olegfafurin

• Open a PR with working implementation of greedy modularity maximization in https://github.com/JuliaGraphs/CommunityDetection.jl (see https://arxiv.org/abs/cond-mat/0309508 and https://arxiv.org/abs/cond-mat/0408187)
• Open a PR with more interface conditions and more graph types for testing in https://github.com/gdalle/GraphsInterfaceChecker.jl

@adfeel220

• Start write up of models and experiments so far on Overleaf
• Last chance to find a continuous-time ILP formulation with a meaningful relaxation
• Think about heuristics to exploit the relaxation of the discrete time ILP formulation

[gdalle]

Wednesday, Nov 22nd

@adfeel220

• Build a bridge between your code and MultiAgentPathFinding.jl
• Does performance get better with a smaller max value for T? Use prioritized planning from MultiAgentPathFinding.jl to get an upper bound
• Read chapters 7 and 11 of Guillaume's thesis (InferOpt + learning MAPF)
• Could the integrality gap increase with the fraction of conflict points? In the discrete time case
• Exploit linear relaxation inside prioritized planning:
  • Max probability edge => use that as the path instead of the shortest path
  • Conflict table between agents (count the times they interact on vertices & edges) => use that to define priorities

@olegfafurin

• Flesh out interface with the goal of presenting it to the community meeting on Thursday 23rd
• Add tests to Newman greedy algorithm
• Pick a new one and read the article

@gdalle

• Review PRs by Oleg
• Read parts of the report by Chun-Tso
• Brush up on decomposition methods in case the LP is still too slow

[gdalle]

Tuesday, Nov 28th

@adfeel220

• Modify the discrete time formulation so that the relaxation makes sense: focus on sum of costs, agents must be at the arrival point at $T$, zero-cost loop
• Finish formulation write up and ping me
• Start working on a new pipeline: Lagrange relaxation + prioritized planning with modified weights => MultiAgentPathfinding.jl

@olegfafurin

• Add more conditions for graphs interface
• Make greedy community PR type-generic, think about in which situations this can be useful
• Profile it to see where the functions take time (on a big graph) => https://gdalle.github.io/IntroJulia/performance.html
• Read https://link.aps.org/doi/10.1103/PhysRevE.70.066111 to see how the greedy method is improved

@gdalle

• Proofread Overleaf
• Think about what agents do at the end of time

[gdalle]

Wednesday Dec 6th

@olegfafurin

• Investigate which operations take the most of the time on larger graphs (stochastic block models)
• Another implementation of the faster method in the second paper
• Forget about interface definition

@adfeel220

• Stopping criterion: certain number of gradient steps / stabilization of the prices
• Run prioritized planning after LR with modified costs to ensure feasible path
• In A*, use shortest path with default costs as a lower bound for the cost of the remaining path (v, t)
• Step size usually changes along gradient descent: for instance $\eta / t^\alpha$
• Study the performance of your storage method and the resulting type instabilities

@gdalle

• Re-read the Newman paper to figure out if we need tried as a set
• Take charge of interface definitoin

[gdalle]

Wednesday Dec 13th

@olegfafurin

• For the first algorithm (2004), think about whether removing the duplicate check changes the overall complexity or not
• Make it run on a graph with $n = 10^6$ by removing quadratic storage (switch e to a sparse matrix)
• Start implementing the second algorithm (2006), first with a basic sparse matrix and then with the cursed max heaps

@adfeel220

• Suggested pipeline:
  1. Use Lagrange relaxation to find modified costs that discourage conflicts
  2. If necessary, run prioritized planning with these modified costs (and possibly modified permutation? don't be unfair)
• Comparison with prioritized planning has two sides:
  • When prioritized planning finds a feasible solution, we want to find a better one => compare solution costs after various amounts of LR. X axis = nb of agents, Y axis = quality of solution, various points / bars corresponding to various time budgets
  • When prioritized planning doesn't find a feasible solution, we want to find one => create instances where LR succeeds
• Keep the simplest hypothesis everywhere: stay at arrival for ILPs, disappear at arrival for LR
• Theoretical question: how interesting is it to be able to modulate costs time-wise and agent-wise in prioritized planning? Kinda like https://ojs.aaai.org/index.php/AAAI/article/view/4758
• Find a deterministic way to break ties in the Lagrange relaxation to eliminate endless rivalry

[gdalle]

Tuesday Dec 19th

@olegfafurin

• Fix the test bug
• Revert to simple dense storage for the first paper
• Check that it does not allocate (BenchmarkTools.jl) and type-stable (JET.jl)
• Start an Overleaf for the report with an idea of the plan

For later:

• Implement second paper with
  1. built-in sparse structures
  2. their custom stuff

@adfeel220

• Make algorithms deterministic
  • solve endless rivalries in an arbitrary way
  • make the graphs about number of gradient steps rather than time spent
  • don't mix LR and PP
• Track value of Lagrange function because it is a lower bound on the true objective (chap 16 of Network flows) => compare the feasible solution of priorized planning with $L(\mu)$ to get a stopping criterion
• Picking a good permutation for prioritized planning

[gdalle]

Vacations

@olegfafurin

• Leftover tasks from last week
• Create repo for experiments using your fork of Graphs.jl, and invite me
• Write the report (https://www.epfl.ch/schools/ic/wp-content/uploads/2023/03/IC-Quick-Guide_Research-Projects_Apr2023.pdf)

Sections

• Introduction:
  • on graphs and community detection (find some more papers to set the scene)
  • on Julia (with Julia: A Fresh Approach to Numerical Computing for instance, or https://www.youtube.com/live/kc9HwsxE1OY?feature=shared)
• Mathematical model
  • describe modularity maximization
  • discuss the differences with other dominant community detection approaches
  • pseudocode for the 2 papers
  • limitations in terms of scalability
• Implementation
  • fill in the gaps, point out what was missing from the papers
  • justify your choices of data structures, formulation, etc.
  • how you exploit the features of the language (type genericity, abstraction with the Graphs interface)
  • how you tried to optimize performance (type stability, allocations)
• Results
  • testing correctness
  • error in the seminal paper (verify it with arbitrary precision numbers)
  • performance measurements, comparison to networkx in terms of speed and genericity
  • other application of your choice on real data (https://snap.stanford.edu/data/)
  • good example for usefulness of type genericity?

@adfeel220

• Debug Lagrange relaxation: lower bound should nearly always go up, and remain below the upper bound
• Results section: what are the questions we are interested in?
  • Why can't we scale integer (linear) programming solvers? How do continuous and discrete time compare?
  • How far can we scale Lagrange Relaxation + Prioritized Planning? Does it solve problems PP couldn't solve? Does it solve other problems better than PP? Show + explain where it works and where it fails
• Write about the respective optimalities of LR, feasible solution of LR, and PP. We may find suboptimal solutions, or no solution at all

@gdalle

• Read new parts of the report
• https://www.ens-lyon.fr/DI/wp-content/uploads/2012/01/LagrangianRelax.pdf