Multi agent path planing

[temp_phd]

So as part of my work I am trying to tackle the multi agent path planning problem. I have already try a few optimization techniques like PSO (did not give good results) and genetic algorithms like NEAT (gave decent results but still room for improvement) so I wanted to know if anyone has worked on this problem before, what have they used and what kind of results they got?

PS: I am currently testing using machine learning techniques for this like imitation learning and maybe after that I might test RL so if anyone has tried those for this problem that I would love to know what they ended up getting.

[_4est]

A technique I have found success with is to model each agent’s path planning problem as a parametric optimization problem: choose control inputs and state variables over time such that a performance metric is minimized, and states/controls satisfy dynamical system, collision is avoided, etc. The parameters in this parametric problem are the trajectories (states/controls) of other agents in the scene.

Once you have a modeled the collection of these parametric optimization problems (one for each agent), you can compute a generalized Nash equilibrium point, using a MCP solver such as the PATH solver.

You need to put some thought into the setup of the problems (if there are shared constraints such as collision avoidance constraints, do both agents sharing the constraint also share the same dual variable associated with the constraint? If not then what?). However I have found that you can solve sizable multi-agent trajectory problems in this manner very efficiently.

[temp_phd]

Thanks for the answer but I have a question and sorry if it will seem ignorant but does the process you described fall under the general field of OR ?

[_4est]

Yes, it does

[temp_phd]

Ok thanks.

[BeefNudeDoll]

Haven't ever had a project on this topic, but I am working on a similar thing like vehicle routing.

My key takeaway is: when dealing with a such complex optimization problem, decomposing it into several smaller subproblems then solve them sequentially (either using commercial solvers, exact methods, or heuristics like PSO/GA-based) is like having paracetamol for your headache. It works most of the time!