快速探索隨機樹輔助之擬剛體編隊設計

Abstract

本研究之主要目的為發展一套具有可變隊形以及避障功能之多載具路徑規劃方案。我們將擬剛體的形變理論應用在多載具的編隊設計上，使得整個隊伍的形狀可由一組空間齊性形變參數來規範，我們將它稱為擬剛體隊伍。擬剛體隊伍容許旋轉、拉伸、切變以及前面三種形變之組合，相較於剛體隊形，我們的隊伍較能夠適應複雜環境的需求，且同時保有極佳的隊形維持能力。此外我們所提出的編隊設計方案還有另一項優點，即隊伍中載具的數目不受限制，不管是載具的新增或減少，皆不會造成求解形變參數時的困擾。在整套路徑規劃方案中，利用快速探索隨機樹(RRT)並配合軌跡平滑以及虛擬障礙物法做全域性的路徑篩選後，建構出一條符合載具曲率限制的隊伍中心路徑，最後藉由這條路徑並透過擬剛體隊形來完成多載具的路徑規劃。我們所提出的多載具路徑規劃方案，可適應於多種不同的環境並保持隊伍的整體性。根據實例設計結果，我們所提出的方案是可行且有效的。

The main purpose of this research is to develop a path planning scheme for multi-vehicle systems, which can produce collision-free paths for the vehicles in the system by changing the formation of system. We apply the pseudo-rigid body theory to the formation design. The formation of system can be determined by a homogenous deformation tensor. Such concept is called the Pseudo-Rigid Formation (PRF). PRF are allowed to rotate, stretch, shear and the combinations of the previous three types of deformation. Comparing with rigid body formation, PRF can adapt to the environments more easily during path planning, and PRF also has a good ability of maintaining the uniformity of system. Another feature of our approach is that it allows to add/remove other vehicles into/from the formation gracefully. And the number of vehicles in the system will not affect the complexity of calculating the deformation tensor. In order to obtain a smooth path for the center of formation and reserve enough space for the formation design, the method of Rapidly-exploring Random Tree (RRT) is used along with some path-smoothing algorithms and potential field methods. The concept of virtual obstacles is introduced to deal with the limitations of the capability of the vehicles in tracing the curved paths. A few design criteria are then adopted to find the suitable PRF. Our approach can be used in many environments without the problem of trapping in local minimum. The design examples show that the proposed scheme is feasible and effective.