We introduce a simple tree growth process that gives rise to a new two-parameter family of discrete fragmentation trees that extends Ford's alpha model to multifurcating trees and includes the trees obtained by uniform sampling from Duquesne and Le Gall's stable continuum random tree. We call these new trees the alpha-gamma trees. In this thesis, we obtain their splitting rules, dislocation measures both in ranked order and in sized-biased order, and we study their limiting behaviour. We further extend the underlying exchangeable fragmentation processes of such trees into partly exchangeable fragmentation processes by weakening the exchangeability. We obtain the integral representations for the measures associated with partly exchangeable fragmentation processes and subordinator of the tagged fragments. We also embed the trees associated with such processes into continuum random trees and study their limiting behaviour. In the end, we generate a three-parameter family of partly exchangeable trees which contains the family of the alpha-gamma trees and another important two-parameter family based on Poisson-Dirichlet distributions.

In this work, we are interested in Growth of Galton-Watson trees under two different models: (1) Galton-Watson (GW) forests with lifetimes and/or immigrants, and (2) Galton-Watson forests with mutation, which we call Galton-Watson-Clone-Mutant forests, or GWCMforests. Under each model, we study certain consistent families (Fλ)λ≥0 of GW/GWCM forests and associated decompositions that include backbone decomposition as studied by many authors. Specifically, consistency here refers to the property that for each μ ≤ λ, the forest Fμ has the same distribution as the subforest of Fλ spanned by the blue leaves in a Bernoulli leaf colouring, where each leaf of Fλ is coloured in blue independently with probability μ/λ. In the first model, the case of exponentially distributed lifetimes and no immigration was studied by Duquesne and Winkel and related to the genealogy of Markovian continuous-state branching processes (CSBP). We characterise here such families in the framework of arbitrary lifetime distributions and immigration according to a renewal process, and show convergence to Sagitov’s (non-Markovian) generalisation of continuous-state branching renewal processes, and related processes with immigration. In the second model, we characterise such families in terms of certain bivariate CSBP with branching mechanisms studied previously by Watanabe and show associated convergence results. This is related to, but more general than Bertoin’s study of GWCM trees, and also ties in with work by Abraham and Delmas, who study directly some of the limiting processes.

Tato diplomová práce práce se zabývá plánováním cesty všesměrového mobilního robotu pomocí algoritmu RRT (Rapidly-exploring Random Tree – Rychle rostoucí náhodný strom). Teoretická část popisuje základní algoritmy plánování cesty a prezentuje bližší pohled na RRT a jeho potenciál. Praktická část práce řeší návrh a tvorbu v zásadě multiplatformní C++ aplikace v prostředí Windows 7 za použití aplikačního frameworku Qt 4.8.0, která implementuje pokročilé RRT algoritmy s parametrizovatelným řešičem a speciálním dávkovým režimem. Tento mód slouží k testování efektivnosti nastavení řešiče pro dané úlohy a je založen na post-processingu a vizualizaci výstupu měřených úloh pomocí jazyka Python. Vypočtené cesty mohou být vylepšeny pomocí zkracovacích algoritmů a výsledná trajektorie odeslána do pohonů Maxon Compact Drive všesměrové mobilní platformy pomocí CANopen. Aplikace klade důraz na moderní grafické uživatelské rozhraní se spolehlivým a výkonným 2D grafickým engine.

Small UAVs are used for low altitude surveillance flights where unknown obstacles can be encountered. These UAVs can be given the capability to navigate in uncertain environments if obstacles are identified. This research presents an obstacle avoidance system for small UAVs. First, a mission waypoint path is created that avoids all known obstacles using a genetic algorithm. Then, while the UAV is in flight, obstacles are detected using a forward looking, onboard camera. Image features are found using the Harris Corner Detector and tracked through multiple video frames which provides three dimensional localization of the features. A sparse three dimensional map of features provides a rough estimate of obstacle locations. The features are grouped into potentially hazardous areas. The small UAV then employs a sliding mode control law on the autopilot to avoid obstacles. This research compares rapidly-exploring random trees to genetic algorithms for UAV pre-mission path planning. It also presents two methods for using image feature movement and UAV telemetry to calculate depth and detect obstacles. The first method uses pixel ray intersection and the second calculates depth from image feature movement. Obstacles are avoided with a success rate of 96%.

This thesis focuses on the design and development of a fixed 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 fluid dy-namic simulations of propeller wake, wind tunnel tests of a 150mm fixed 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 verified by numerous flight 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 flight control law, is designed to attenuate the effects of modelling uncertainties, discrete vertical and head-on wind gusts, and to maintain flight stability and performance requirements at all allowable operating conditions. The controller is implemented in the MAV autopilot hardware with successful close loop flight trials. The flight 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 configuration 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 configuration 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 identifies 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 significant 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 verified with numerous collision detection scenarios.