A message-passing algorithm for multi-agent trajectory planning
We describe a novel approach for computing collision-free global trajectories for p agents with specified initial and final configurations, based on an improved version of the alternating direction method of multipliers (ADMM). Compared with existing methods, our approach is naturally parallelizable and allows for incorporating different cost functionals with only minor adjustments. We apply our method to classical challenging instances and observe that its computational requirements scale well with p for several cost functionals. We also show that a specialization of our algorithm can be used for local motion planning by solving the problem of joint optimization in velocity space.
The paper considers global and local path planning for 
      multiple agents in 2-D with a centralized message-passing algorithm 
      derived from the "three-weight" version of ADMM, an established algorithm. 
      The contributions are clearly stated in the introduction: The authors 
      decompose global planning optimization into several sub-problems they dub 
      "minimizers," which describe various planning objectives that comprise the 
      larger overall problem to be solved. Minimizers are derived for avoiding 
      inter-agent collisions, avoiding collisions with static obstacles, and for 
      maximizing/minimizing kinetic energy or velocity. They also apply their 
      approach to local planning by reformulating joint optimization. 
      The overall concept for using a distributed optimization algorithm 
      for multi-agent path planning is nice; however the results are a 
      little lacking. They do not provide comparisons to other well-known high 
      dimensional path planning techniques, such as A* variants with 
      inflated heuristics or sampling-based methods. For many of these problems, 
      there is also the aspect of replanning given new state or obstacle 
      information. Would this algorithm be amenable to such dynamic or anytime 
      implementations? In that regard, it's hard to see how this formulation 
      would guarantee that certain constraints would always be enforced for 
      early stopping, for example a hard collision or communication constraints. 
      These and other issues regarding the planning problem should be discussed. 
      It's also not clear if this manuscript would appeal to the broader NIPS 
      audience. It would definitely fit into a dedicated planning/robotics 
      meeting, but it's hard to see if this would appeal from an algorithmic 
      viewpoint to other NIPS areas. There are also a few minor items 
      that could be improved in the presentation. First of all, please use a 
      letter other than "n" for the correction messages in your formulations. 
      "n" is already used to describe the number of interior break-points, a 
      major parameter for the overall algorithm. Figure 2-middle and Figure 
      3-left include multiple scales on either the x- or y-axis. In the case of 
      Figure 3-left, I initially thought that the convergence time between 
      optimizing total energy and finding a feasible solution were comparable, 
      when one is several orders of magnitude larger. These figures seem to be 
      an attempt to fit the paper within the page limit but could cause 
      confusion and dilute the impact of the results. Also, with respect to the 
      convergence times reported for local trajectory planning using the 
      proposed approach versus MIQP [12], the authors compare implementations in 
      different programming languages and say the results are not "exactly 
      comparable." Yet, they directly compare the convergence times in Figure 
      3-right. They also state, "our method does not require approximating the 
      search domain by hyperplanes, nor does it require an additional 
      branch-and-bound algorithm," which causes one to further question the 
      direct comparison of convergence times. These results could be clarified.