Abstract
Pipe routing can be briefly formulated as seeking the shortest collision-free pipe paths while meeting certain engineering constraints. This article presents a new rectilinear pipe routing algorithm called Manhattan visibility graph (MVG) by extending the Visibility Graph method used for finding the shortest collision-free paths in Euclidean spaces to Manhattan spaces. Subsequently, the article proves that MVG can theoretically guarantee an optimal solution. Further, the article extends MVG algorithm to surface cases to meet requirements of routing pipes in aero-engine rotational spaces. Unlike previous graph methods that commonly yield more than n nodes (where n is the total number of terminals and obstacle vertices), MVG significantly reduces computation complexity because of containing only n nodes. Finally, numerical computations on a developed pipe routing system are performed to demonstrate the effectiveness and efficiency of the proposed method.