Spatial model and decentralized path planning for construction automation

This thesis presents a decentralized path planning system for multiple construction automatons. The decentralized path planning system consists of a host computer for providing a spatial model, construction automatons, a human interface for supervising the spatial model and automatons, and human operators. Each automaton independently plans its path using the spatial model and local information in real time. The construction site is defined as partially known and unknown environment, the spatial characteristics of the construction site are analyzed, and the corresponding spatial model is developed. Considering technological reality, spatial location accuracy constraints, and economical efficiency, only the essential boundary information is included in the known environment that is represented as a spatial model consisting of cells and a network. (Each automaton realizes the unknown environment using sensors.) The cells are geometric objects and provide the domain for path planning. The network is a topological object and is used to compute the shortest path. Each automaton has its own global and local path planners. The global planner computes the shortest path on the network and provides it to the local planner in terms of a sequence of vertices (sub-goals). While following the sub-goals, the local planner uses CAT algorithm to modify the shortest path to avoid unknown or misplaced obstacles. The CAT algorithm guarantees reachability in the environment that is populated by stationary, moving, and composite obstacles. The decentralized path planning system is stable and robust. Each automaton plans its own path and thus computation is distributed and independent of the number of automatons. The path planning system may not deliver optimal performance because of the independence of each automaton. Instead, the decentralized path planning delivers a reasonable performance in a reasonably complex environment. In some situation, an automaton may fail to arrive at its goal, however, the entire system does not fail.