The Grid-Based Path-Planning Competition

Alarge number of papers have been written that dealwith path planning in grids. These papers contain awide variety of techniques and operate under a wide variety of constraints. All of them offer significant improve-ment over and beyond a basic A * search. But there has been no unified study comparing techniques and measuring the trade-offs implicit in the approaches. While this comparison could be performed by a single individual implementing existing approaches, the overhead of implementing all exist-ing techniques is significant, and the final payoff is small rel-ative to the amount of work performed. Furthermore, there is no guarantee that all implementations will be properly optimized, or that edge cases are handled correctly. This leads to two significant issues. First, it is difficult to identify which existing approaches are best for a given task, and second, it is difficult to evaluate new approaches and assess their strengths and weaknesses. Related to this is the problem of metrics. There are many metrics that can be opti-mized, such as planning time, plan quality, preprocessing n While there have been many papers pub-lished on path planning in grids, there has not been significant work on comparing existing approaches, and it is difficult to evaluate new work in comparison to existing work. After creating a public repository of grid-based path-planning problems I created the Grid-Based Path-Planning Competition (GPPC) to facilitate these comparisons. This article describes the motivation and design of the competition, as well as plans for the future of the competition