Abstract

Many smart city applications such as optimal path planning for multiple transportation robots in factories and warehouses are formulated as highly complex combinatorial optimization problems. Since these problem-solving processes require time-critical control and low energy consumption when executed at the edge of computer networks, a promising approach is to implement high speed solvers on Field Programmable Gate Array (FPGA) by exploiting its parallelism and energy efficiency. Here we focus on a variant of the Multi-Agent Path Finding (MAPF) problem, which is a problem of finding optimal discrete space-time trajectories of the robots that are required to complete transportation requests in a semiconductor fabrication factory as early as possible without colliding with each other. According to our future aim to find a feasible solution to a large-sized problem instance in a distributed manner, the present paper proposes a multi-FPGA implementation of a variant of ‘AmoebaSATslim,’ which is a bio-inspired parallel search algorithm to search for a solution to the Boolean satisfiability problem (SAT). We design an FPGA cluster that links two FPGA boards to tackle a minimal-sized instance for two robots to transport two packages, where each of the boards is responsible for finding the trajectory of each of the robots. The proposed dual-FPGA implementation handles 22,544 variables and achieves up to approximately 17-fold faster execution speed than its software implemented on an x86-based personal computer.