# Concealed Conduit Routing in Building Slabs
## 1 Introduction  
Pipe systems are widely used in vehicles, engines, factories, and refineries to transport fuels, water, air, and raw materials. They are essential components in the manufacturing, chemical, and transportation industries. Many efficient algorithms have been proposed for routing them since the 1970s [1, 2]. Since pipes are utilized in various applications [3, 4, 5, 6], the paradigms, domain representation methods, and limitations of these published algorithms are different. However, they share a common aspect: The target pipes are exposed conduits. That is, they aim to lay out pipes in open spaces or on the surfaces of objects, and the resultant pipes are visible and accessible to the users.  
In modern buildings, there are hoses, conduits, and wire harnesses inside the walls, floors, and ceilings. These pipes are invisible and inaccessible to us but we rely on them to deliver ventilation air, tap water, electrical power, digital signals, and natural gas such that decent living and working conditions can be maintained. In construction industries, these pipes are included in the Mechanical Electronic and Plumbing (MEP) systems and must be carefully planned prior to the construction of the buildings [7, 8, 6].  
Figure 1 reveals the major difference between exposed conduit systems (left part) and concealed conduit systems (right part). The exposed conduits are routed in open spaces or on the surfaces of machinery. They may penetrate the walls to connect terminals residing in different rooms, but their paths do not reside below the surfaces of the walls and the machinery. On the other hand, the concealed pipes are built inside the walls, floors, and ceilings of the building. They wander in the walls, floors, and ceilings to connect terminals. Their paths are laid out within the slabs of the building.  
Solely based on the functionality of transportation, concealed conduits can be replaced with exposed ones. However, concealed conduits possess at least the following advantages over exposed pipes: (1) They do not occupy valuable living space; (2) they do not hinder the operations of machinery and the movement of humans; (3) they do not need supporting racks; (4) they are resilient to intentional or unintentional collisions; (5) and for the sake of aesthetics, they do not produce unpleasant visual effects. Therefore, concealed conduits are widely installed in modern buildings, and routing them is an important issue in building design and construction.  
The complexity and costs of a pipe-routing process are significantly influenced by the characteristics of the workspace [1]. Exposed pipes are laid in open spaces or on the surfaces of machinery [2; 3; 4; 5]. Their workspaces are extensible and more flexible. On the other hand, concealed conduits are buried inside the walls, floors, ceilings, columns, and beams of buildings. Their workspaces are confined within these substructures only and are impossible to extend. Furthermore, staircases, windows, and doors in the buildings significantly reduce the usable portions of the workspace and increase the geometric complexity of the workspaces. To make matters worse, concealed pipes should be buried below the surfaces of these substructures at a certain distance such that they will not be damaged when the surfaces are hammered, decorated, or tiled. Hence, the workspace of a concealed conduit system is much thinner and more limited than expected. The examples shown in Figure 1 reveal the characteristics of the working domains of concealed pipes.  
In addition to overcoming the above challenges, the transportation functionalities, construction costs, and safety regulations must be also taken into consideration when routing concealed conduits. These requirements make laying out concealed conduits more difficult. Conventional piping algorithms are not suitable for arranging concealed conduits. Specialized routing methods and new workspace representations have to be developed to fulfill the piping task.