Application of Randomized Algorithms in Path Planning and Control of a Micro Air Vehicle
This thesis focuses on the design and development of a ﬁxed wing micro air vehicle (MAV) and on the development of randomized sampling based motion planning and control algorithms for path planning and stabilization of the MAV. In addition, the thesis also contains probabilis-tic analyses of the algorithmic properties of randomized sampling based algorithms, such as completeness and asymptotic optimality. The thesis begins with a detailed discussion on aerodynamic design, computational ﬂuid dy-namic simulations of propeller wake, wind tunnel tests of a 150mm ﬁxed wing micro air ve-hicle. The vehicle is designed in such a way that in spite of the various adverse effects of low Reynolds number aerodynamics and the complex propeller wake interactions with the airframe, the vehicle shows a balance of external forces and moments at most of the operating conditions. This is supported by various CFD analysis and wind tunnel tests and is shown in this thesis. The thesis also contains a reasonably accurate longitudinal and lateral dynamical model of the MAV, which are veriﬁed by numerous ﬂight trials. However, there still exists a considerable amount of model uncertainties in the system descrip-tion of the MAV. A robust feedback stabilized close loop ﬂight control law, is designed to attenuate the effects of modelling uncertainties, discrete vertical and head-on wind gusts, and to maintain ﬂight stability and performance requirements at all allowable operating conditions. The controller is implemented in the MAV autopilot hardware with successful close loop ﬂight trials. The ﬂight controller is designed based on the probabilistic robust control approach. The approach is based on statistical average case analysis and synthesis techniques. It removes the conservatism present in the classical robust feedback design (which is based the worst case de-sign techniques) and associated sluggish system response characteristics. Instead of minimizing the effect of the worst case disturbance, a randomized techniques synthesizes a controller for which some performance index is minimized in an empirical average sense. In this thesis it is shown that the degree of conservatism in the design and the number of samples used to by the randomized sampling based techniques has a direct relationship. In particular, it is shown that, as the lower bound on the number of samples reduces, the degree of conservatism increases in the design. Classical motion planning and obstacle avoidance methodologies are computationally expen-sive with the number of degrees of freedom of the vehicle, and therefore, these methodologies are largely inapplicable for MAVs with 6 degrees of freedom. The problem of computational complexity can be avoided using randomized sampling based motion planning algorithms such as probabilistic roadmap method or PRM. However, as a pay-off these algorithms lack algorith-mic completeness properties. In this thesis, it is established that the algorithmic completeness properties are dependent on the choice of the sampling sequences. The thesis contains analy-sis of algorithmic features such as probabilistic completeness and asymptotic optimality of the PRM algorithm and its many variants, under the incremental and independent problem model framework. It is shown in this thesis that the structure of the random sample sequence affects the solution of the sampling based algorithms. The problem of capturing the connectivity of the conﬁguration space in the presence of ob-stacles, which is a central problem in randomized motion planning, is also discussed in this thesis. In particular, the success probability of one such randomized algorithm, named Obsta-cle based Probabilistic Roadmap Method or OBPRM is estimated using geometric probability theory. A direct relationship between the weak upper bound of the success probability and the obstacle geometric features is established. The thesis also contains a new sampling based algorithm which is based on geometric random walk theory, which addresses the problem of capturing the connectivity of the conﬁguration space. The algorithm shows better performance when compared with other similar algorithm such as the Randomized Bridge Builder method for identical benchmark problems. Numerical simulation shows that the algorithm shows en-hanced performance as the dimension of the motion planning problem increases. As one of the central objectives, the thesis proposes a pre-processing technique of the state space of the system to enhance the performance of sampling based kino-dynamic motion plan-ner such as rapidly exploring random tree or RRT. This pre-processing technique can not only be applied for the motion planning of the MAV, but can also be applied for a wide class of vehicle and complex systems with large number of degrees of freedom. The pre-processing techniques identiﬁes the sequence of regions, to be searched for a solution, in order to do mo-tion planning and obstacle avoidance for an MAV, by an RRT planner. Numerical simulation shows signiﬁcant improvement over the basic RRT planner with a small additional computa-tional overhead. The probabilistic analysis of RRT algorithm and an approximate asymptotic optimality analysis of the solution returned by the algorithm, is also presented in this thesis. In particular, it is shown that the RRT algorithm is not asymptotically optimal. An integral part of the motion planning algorithm is the capability of fast collision detection between various geometric objects. Image space based methods, which uses Graphics Pro-cessing Unit or GPU hardware, and do not use object geometry explicitly, are found to be fast and accurate for this purpose. In this thesis, a new collision detection method between two convex/non-convex objects using GPU, is provided. The performance of the algorithm, which is an extension of an existing algorithm, is veriﬁed with numerous collision detection scenarios.