A Hierarchy MCTS Algorithm for The Automated PCB Routing

The PCB electronic components placement and routing are very importance for the Printed Circuit Board (PCB) design, which needs plenty of time and precision. Some algorithms have been proposed for automatic electronic components placement and routing. However, existing methods can’t meet the precision or efficiency demand for the PCB design. In this work, we propose a hierarchy MCTS algorithm for the PCB routing. The PCB is mapped to a grid map. Hence, the PCB routing can be converted to an optimal route searching game from the start pin to the end pin. The optimal goal is to find the shortest routes for the pins on the PCB by following the routing rules. Then, the hierarchy MCTS is employed to find the optimal routes for the PCB routing. The hierarchy MCTS consists of two MCTSs. The first MCTS will generate a sketchy route and a subgoal for the second MCTS. Hence, the second MCTS can obtain two optimal routes from the start pin to the subgoal and from the subgoal to the end pin. The two optimal routes will be concatenated as the final optimal route. The advantage of using hierarchy MCTS is that the second MCTS can search more efficiently according to the subgoal generated by the first MCTS and generate a better route. After experiments, our proposed algorithm can obtain the optimal routes and improve 15.38% computing efficiency, compared with existing methods.