A Hierarchical Heuristic for Clustered Steiner Trees in the Plane with Obstacles
This addresses the need for modeling decentralized and multipoint coordination of agents in constrained 2D domains, but appears incremental as it builds on existing Steiner tree methods.
The paper tackled the problem of computing multiple disjoint Euclidean Steiner trees that avoid obstacles in the plane, using a hierarchical approach with bundling operations, and demonstrated feasibility and attractive performance in computational experiments.
Euclidean Steiner trees are relevant to model minimal networks in real-world applications ubiquitously. In this paper, we study the feasibility of a hierarchical approach embedded with bundling operations to compute multiple and mutually disjoint Euclidean Steiner trees that avoid clutter and overlapping with obstacles in the plane, which is significant to model the decentralized and the multipoint coordination of agents in constrained 2D domains. Our computational experiments using arbitrary obstacle configuration with convex and non-convex geometries show the feasibility and the attractive performance when computing multiple obstacle-avoiding Steiner trees in the plane. Our results offer the mechanisms to elucidate new operators for obstacle-avoiding Steiner trees.