Title of paper: 



(1) Towards Bundling Minimal Trees in Polygonal Maps

(2) Path Planning On Hierarchical Bundles With Differential Evolution

(3) Bundling n-Stars in Polygonal Maps




Authors:



Victor Parque, Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo, Japan, (+81)-3-5286-3249, parque@aoni.waseda.jp

Tomoyuki Miyashita,  Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo, Japan, (+81)-3-5286-3249, tomo.miyashita@waseda.jp



Corresponding Author: Victor Parque (parque@aoni.waseda.jp)



Abstract:



Minimal trees in polygonal maps aim at minimizing the connectivity in a network while avoiding obstacle collision. Being closely related to the Steiner Tree Problem, yet with a different scope, minimal trees aim at connecting origin-destination nodes in a hierarchical bipartite network, to allow the efficient transport of information, goods, resources and people. 

In our work, we propose a method to tackle the bundling problem of minimal trees in modular bipartite networks by using a two-layer optimization based on Differential Evolution with a convex representation of coordinates. 

Our computational experiments in polygonal domains considering both convex and non-convex geometry show the feasibility and the efficiency of the proposed approach.




Criteria List: B, D, G



Statement on Criteria:



Criterion B: 


The research on minimal trees has its origins in the 30's with the Steiner tree problem, and has been studied widely to design of communication and transport networks optimally.  We present an algorithm that solves the problem of computing minimal trees in complex and real-world maps with high success.  Though benchmarks are unexistent for algorithmic comparison, it is possible to observe the efficiency, effectiveness and practical implications based on the difficulty of the maps that can be solved, as well as the the sophistication of the trees obtained.  



In our experiments, we have included different geometric configurations of obstacles and diverse number of edges in the tree. This might, for instance, denote nodes sparsely distributed in cluttered environments. As such, the result is a tree minimizing the inter-connectivity among source and destination nodes, which allows for optimal means in transport and communication of multi-agent systems.



Criterion D: 
In addition to the significant improvement in sophistication of the environments, we introduce (1) path planning using Evolutionary Computing and convex representations of the free navigable space ( which was successfully tested on Differential Evolution, Particle Swarm Optimization and their latest variants), and (2) novel nature-inspired operators for computing minimal trees.




Criterion G: It is clear that minimal trees is an important and difficult problem that has been addressed using a wide variety of techniques. The Steiner tree problem, and numerous variations, are even more widely studied and significant in the field.




Citation:



V. Parque, T. Miyashita, "Towards Bundling Minimal Trees in Polygonal Maps", In ACM Genetic and Evolutionary Computation Conference (GECCO), Workshop on Intelligent Operations Management in the Energy Sector, To Appear.
https://drive.google.com/open?id=1S8uW12XxbzRv3QQN3Xb_E-ovpNThMtkY


V. Parque, T. Miyashita, "Path Planning On Hierarchical Bundles With Differential Evolution", 9th International Conference on Swarm Intelligence, Shanghai, June 17 - 22, 2018, To Appear

.
https://drive.google.com/open?id=1sRRiU0Tz8ybFStixMOOLyAy7vUEcSNrx

V. Parque, T. Miyashita, "Bundling n-Stars in Polygonal Maps", in 29th International Conference on Tools with Artificial Intelligence, Nov 6, 2017 - Nov 8, 2017, Boston, To Appear.
https://drive.google.com/open?id=1FfU1UF0jDq8oj2F_o-Os7AYKJmbgsb-0





Prize Money: Any prize money is to be divided evenly among the co-authors.





Statement to the Judges: 


Relevance of problem: Minimal trees are relevant to enable efficient communication and transportation in cluttered environments (IoT, collaborative robots, wireless communications, multiagents, vehicle networks). Our approach computes minimal trees by compounding edges to build optimal networks. Our experiments have shown the feasibility to obtain minimal trees in environments with complex obstacles and arbitrary network configurations. The effectiveness and efficiency to compute minimal trees in diverse environments show the generalization ability for problems involving communication, transportation and network design.



Novel approach: Our appraoch introduces (1) a convex (canonical) representation of the navigable space for planning based on Evolutionary Computation, and (2) novel nature-inspired operators for computing minimal trees.



General Type: Differential Evolution