Optimizing formation movement over heteregeneous terrain /

by Cesur, Fatih.; School (U.S.), Naval Postgraduate

Formation movement is vital to preserve security among its units during military operations. We plan movement of a military formation over real, or simulated terrain, maximally preserving the relative positions of units in formation while it avoids barriers, and while its units avoid obstacles. Terrain is divided into homogeneous cells (say, squares), and a pair of neighboring cells is adjacent if the formation can transit between these cells while avoiding barriers with sufficient clearance. We induce a graph from these adjacencies, and determine the movement cost on each arc with a fine time-step simulation that finds local movement vectors to preserve relative formation position while avoiding approach too close to barriers or obstacles (this emulates solving differential equations with Euler's method). We then nominate an origin and a destination, select a shortest path, and repeat the time-step simulation over this path to determine the individual positions of each unit as the formation makes its transit. Game designers and robot controllers have published schemes to guide formation movement, but their movements can penetrate barriers, and myopically get caught in cul-de-sacs. By contrast, we guarantee that if a path exists that avoids these pitfalls, we will find it.