Explore-and-Fuse: A Physarum-Inspired Approach to the Steiner Tree Problem

Overview

This project presents a novel explore-and-fuse approach to solving difficult problems that cannot be solved by traditional divide-and-conquer. This approach is inspired by Physarum, a unicellular slime mold capable of solving the traveling salesman and Steiner tree problems. Besides exhibiting individual intelligence, Physarum can also share information with other Physarum organisms through fusion. These characteristics of Physarum inspire us to spawn many Physarum organisms to explore the problem space in parallel, with each organism gathering information and forming partial solutions pertaining to a local region of the prob- lem space. When the organisms meet, they fuse and share information, eventually forming one organism which has a global view of the problem and can apply its intelligence to find an overall solution to the problem. We demonstrate this novel approach on the NP-hard Steiner tree problem, developing the Physarum Steiner Algorithm. We then apply the Physarum Steiner Algorithm to designing chips, creating road networks, and solving broadband in- equality with more efficient fiber optic cable routing. The Physarum Steiner Algorithm is of particular interest due to its ability to leverage parallel processing, avoid obstacles, and operate on various shapes and topological surfaces including the rectilinear grid.

Awards (1)

• Central Intelligence Agency: First Award: $1000 award $1,000

Competition history

• ISEF 2022 Systems Software · Entry SOFT043 · Atlanta, Georgia, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.