An Emergent Pattern Formation Approach to Dynamic Spatial Problems via Quantitative Front Propagation and Particle Chemotaxis
Jeff Jones
Wavefront based computation has recently been proposed as an unconventional method for a number of spatial geometry and path planning problems, exploiting the parallel search and uniform speed of front propagation. Although posited in one of the original descriptions of path planning by reaction-diffusion systems, dynamic approaches to spatial problems using chemical means remain hampered by both the slow propagation speed and practical difficulties in reconfiguring chemical implementations. A method is presented where the front propagation and path elicitation are concurrently applied in a software model using a multi-layered approach based on a simple, quantitative method of wave propagation and a path traversal method based on chemotactic particle motion. The method can accommodate dynamically changing environments and provide a dynamic representation of path choice. The quantitative propagation method also allows the assignment of costs to certain paths by restricting the propagation along the path by constricting the path width. The method is applied to classical and dynamic instances of geometry problems (skeletonisation and Voronoi Diagram approximation by negative chemotaxis) and path planning (shortest path by positive chemotaxis) and example results are presented.