Cette thèse a pour objet d’étude divers modèles de marches aléatoires sur les arbres aléatoires.Nous nous sommes consacrés principalement aux aspects qui relevaient à la fois de la théorie des probabilités et de la théorie ergodique. Notre premier modèle est celui des marches aléatoires sur les arbres à longueurs récursives(qui généralise un modèle apparaissant dans un travail récent de Curien et Le Gall). Nous montrons pour ce modèle sous des conditions très générales qu’un phénomène appelé « chute de dimension » se produit pour la mesure harmonique et donnons une formule assez explicite permettant de calculer cette dimension.En utilisant les outils développés pour ce dernier modèle, nous nous intéressons à la marche aléatoire lambda-biaisée sur un arbre de Galton-Watson infini, pour lequel de nombreuses conjectures sont toujours ouvertes. Notre approche nous permet de calculer la dimension de la mesure harmonique en fonction de la loi de la conductance de l’arbre. C’est un résultat nouveau qui nous permet de vérifier numériquement certaines de ces conjectures ouvertes.Le reste de la thèse porte sur un modèle très riche appelé marche aléatoire sur un arbre pondéré aléatoire. D’abord dans le cas transient, où nous montrons par une approche différente de celle des parties précédentes que le phénomène de chute de dimension se produit. Puis sur un cas récurrent appelé sous-diffusif, où nous nous intéressons à la vitesse de convergence vers 0 de la conductance entre la racine et le niveau n de l’arbre lorsque n tend vers l’infini. Nous montrons que la loi limite de cette conductance renormalisée par son espérance est la limite de la martingale de Mandelbrot. / The subject of this thesis is the study of various models of random walks on random trees, with an emphasis on the aspects that fall at the intersection of probability theory and ergodic theory. We called our first model “random walks on Galton-Watson trees with recursive lengths”.It generalizes a model appearing in a recent work by Curien and Le Gall. We show that under fairly general assumptions, a phenomenon called “dimension drop” holds for this model and we give a formula for this dimension. Using the tools developed for the study of the previous model, we turn to the case oft ransient lambda-biased random walks on infinite Galton-Watson trees, for which many famous problems are still open. Our approach allows us to compute the dimension of the harmonic measure as a function of the law of the conductance of the tree. With this new result, we check numerically the validity of some twenty-year-old conjectures.The remainder of this thesis is about a very rich model called random walk on a random weighted Galton-Watson tree. First, we study the transient case, where we show with a different method than in the previous parts, that the dimension drop phenomen on occurs. Then we turn to a recurrent case called subdiffusive and we investigate the rate of decay of the conductance between the root and the n-th level of the tree, as n goes to infinity. We prove that this conductance, suitably renormalized converges to the limit of the Mandelbrot martingale.

Almost two thirds of the Earth's surface is covered in ocean, and yet, only about 5% of it is mapped. There are an unknown amount of sunken ships, planes, and other artifacts hidden below the sea. Extensive search via boat and a sonar tow fish following a standard lawnmower pattern is used to identify sites of interest. Then, if a site has been determined to potentially be historically significant, the most common next step is a survey by either a human dive team or remotely operated vehicle. These are time consuming, error prone, and potentially dangerous options, but autonomous underwater vehicles (AUVs) are a possible solution. This thesis introduces a system for automatically generating paths for AUVs to survey and map shipwrecks. Most AUVs include software to set a lawnmower path for a given region of ocean, and individualized paths can be set via specifying GPS encoded nodes for the AUV to pass through. This thesis presents an algorithm for generating an individualized path that permits the AUV, equipped with a camera to "see" all sides of a region of interest (i.e. a shipwreck). This allows the region of interest to be completely documented. Photogrammetry can then be used to reconstruct a three-dimensional model, but a path is needed to do so. Paths are generated by a probabilistic roadmap algorithm that uses a rapidly-exploring random tree to quickly cover the volume of exploration space and generate small maps with good coverage. The roadmap is constructed out of nodes, each having its own weight. The weight of a given node is calculated using an objective function which measures an approximate view coverage by casting rays from the virtual view and intersecting them with the region of interest. In addition, the weight of a node is increased if this node allows the AUV to see a new side of the region of interest. In each iteration of the algorithm, a node to expand off of is selected based off its location in space or its high weight, a new node with a given amount of freedom is generated, and then added to the roadmap. The algorithm has degrees of freedom in position, pitch, and yaw as well as the objective function to encourage the path to see all sides of the region of interest. Once all sides of the region of interest have been viewed, a path is determined to be complete. The algorithm was tested in a virtual world where the virtual camera acted as the AUV. All of the images collected from our automatically generated path were used to create 3D models and point clouds using photogrammetry. To measure the effectiveness of our paths versus the pre-packaged lawnmower paths, the 3D models and point clouds created from our algorithm were compared to those generated from running a standard lawnmower pattern. The paths generated by our algorithm captured images that could be used in a 3D reconstruction which were more detailed and showed better coverage of the region of interest than those from the lawnmower pattern.

M.Sc., Faculty of Sciences, University of the Witwatersrand, 2011 / Abstract This dissertation is concerned with discrete global optimization of nonlinear problems. These problems are constrained and unconstrained and are not easily solvable since there exists multiplicity of local and global minima. In this dissertation, we study the current methods for solving such problems and highlight their ine ciencies. We introduce a new local search procedure. We study the rapidly-exploring random tree (RRT) method, found mostly in the research area of robotics. We then design two global optimization algorithms based on RRT. RRT has never been used in the eld of global optimization. We exploit its attractive properties to develop two new algorithms for solving the discrete nonlinear optimization problems. The rst method is called RRT-Optimizer and is denoted as RRTOpt. RRTOpt is then modi ed to include probabilistic elements within the RRT. We have denoted this method by RRTOptv1. Results are generated for both methods and numerical comparisons are made with a number of recent methods.

<p>Many of the applications that have been proposed for future small unmanned aerial vehicles (UAVs) are at low altitude in areas with many obstacles. A vital component for successful navigation in such environments is a path planner that can find collision free paths for the UAV.</p><p>Two popular path planning algorithms are the probabilistic roadmap algorithm (PRM) and the rapidly-exploring random tree algorithm (RRT).</p><p>Adaptations of these algorithms to an unmanned autonomous helicopter are presented in this thesis, together with a number of extensions for handling constraints at different stages of the planning process.</p><p>The result of this work is twofold:</p><p>First, the described planners and extensions have been implemented and integrated into the software architecture of a UAV. A number of flight tests with these algorithms have been performed on a physical helicopter and the results from some of them are presented in this thesis.</p><p>Second, an empirical study has been conducted, comparing the performance of the different algorithms and extensions in this planning domain. It is shown that with the environment known in advance, the PRM algorithm generally performs better than the RRT algorithm due to its precompiled roadmaps, but that the latter is also usable as long as the environment is not too complex. The study also shows that simple geometric constraints can be added in the runtime phase of the PRM algorithm, without a big impact on performance. It is also shown that postponing the motion constraints to the runtime phase can improve the performance of the planner in some cases.</p> / Report code: LiU–Tek–Lic–2006:10.

La première partie de cette thèse s’inscrit dans le domaine des cartes aléatoires, qui est un sujet à la frontière des probabilités, de la combinatoire et de la physique statistique. Nos travaux complètent une série de résultats de convergence de différents modèles de cartes aléatoires vers la carte brownienne, qui est un espace métrique compact aléatoire. Plus précisément, on montre que la limite d’échelle d’une carte de loi uniforme sur l’ensemble des cartes biparties enracinées à n arêtes, munie de la distance de graphe renormalisée par (2n)^(−1/4), est, au sens de Gromov–Hausdorff, la carte brownienne. Pour prouver ce résultat, les arguments importants sont d’une part l’utilisation d’une bijection combinatoire entre cartes biparties et arbres multitypes, et d’autre part des théorèmes de convergence pour les arbres de Galton–Watson multitypes étiquetés. Dans un deuxième temps, le but est de présenter une théorie des excursions pour le mouvement brownien indexé par l’arbre brownien. De manière analogue à la théorie d’Itô des excursions pour le mouvement brownien, chaque excursion correspond à une composante connexe du complémentaire des zéros du mouvement brownien indexé par l’arbre, et l’excursion est définie comme un processus indexé par un arbre continu. On explique comment mesurer la longueur de la frontière de ces excursions, de sorte que la famille de ces longueurs coïncide avec les sauts d’un processus de branchement à temps continu de mécanisme de branchement stable d’indice 3/2. De plus, conditionnellement aux longueurs des frontières, les excursions sont indépendantes et leur loi conditionnelle est déterminée à l’aide d’une mesure d’excursion explicite que l’on introduit et décrit. Dans ce travail, le serpent brownien apparaît comme un outil particulièrement important. / The first part of this thesis concerns the area of random maps, which is a topic in between probability theory, combinatorics and statistical physics. Our work complements several results of convergence of various classes of random maps to the Brownian map, which is a random compact metric space. More precisely, we prove that the scaling limit of a map which is uniformly distributed over the class of rooted planar maps with n edges, equipped with the graph distance rescaled by (2n)^(−1/4), is, in the Gromov-Hausdorff sense, the Brownian map. To establish this result, the main arguments are the use of a combinatorial bijection between bipartite maps and multitype trees, together with convergence theorems for Galton-Watson multitype trees. We then aim to develop an excursion theory for Brownian motion indexed by the Brownian tree. Analogous to the Itô excursion theory for Brownian motion, each excursion corresponds to a connected component of the complement of the zero set of the tree-indexed Brownian motion, and the excursion is defined as a process indexed by a continuous tree. We explain how to measure the length of the boundary of these excursions, in a way that the collection of these lengths coincides with the collection of jumps of a continuous-state branching process with a 3/2-stable branching mechanism. Moreover, conditionally on the boundary lengths, the excursions are independent and their conditional distribution is determined in terms of an excursion measure that we introduce and study. In this work, the Brownian snake appears as a particularly important tool.

This thesis deals with analyses of problems of path planning by means Rapidly-exploring Random Trees (RRT) algorithm. The teoretic part described of basic terms and navigation mobile robots. There are localization, mapping and path planning parts of navigation. Then it is description overview of localization of methods and overview of robot path planning methods. The practical describes implementation of proposed method in Delphi. The best method for path planning of robot using RRT algorithm. For reservation universal communications interface is application creation like dynamic library.

Many of the applications that have been proposed for future small unmanned aerial vehicles (UAVs) are at low altitude in areas with many obstacles. A vital component for successful navigation in such environments is a path planner that can find collision free paths for the UAV. Two popular path planning algorithms are the probabilistic roadmap algorithm (PRM) and the rapidly-exploring random tree algorithm (RRT). Adaptations of these algorithms to an unmanned autonomous helicopter are presented in this thesis, together with a number of extensions for handling constraints at different stages of the planning process. The result of this work is twofold: First, the described planners and extensions have been implemented and integrated into the software architecture of a UAV. A number of flight tests with these algorithms have been performed on a physical helicopter and the results from some of them are presented in this thesis. Second, an empirical study has been conducted, comparing the performance of the different algorithms and extensions in this planning domain. It is shown that with the environment known in advance, the PRM algorithm generally performs better than the RRT algorithm due to its precompiled roadmaps, but that the latter is also usable as long as the environment is not too complex. The study also shows that simple geometric constraints can be added in the runtime phase of the PRM algorithm, without a big impact on performance. It is also shown that postponing the motion constraints to the runtime phase can improve the performance of the planner in some cases. / <p>Report code: LiU–Tek–Lic–2006:10.</p>

No description available.

Efter att EU införde ett ramverk år 2000 rörande regionens vattenanvändning, vattendirektivet, beslöt Sveriges regering att från och med sommaren 2020 ompröva rikets vattendammar. I de fall rådande vattenanvändning inte uppfyller de krav som anges i ramverket kan dammutrivning bli aktuellt. Syftet med studien är undersöka och utveckla en metod att utvärdera förändringar av strömhabitat uppströms ett vattendrag efter en dammutrivning. Studieområdet utgörs och begränsas av datamängden i form av flygfoton insamlade med UAV vid två tillfällen över samma område. Även batymetriska data över vattendragets botten från en bottenskanning har använts således även Lantmäteriets nationella höjdmodell. Två fotogrammetriprogram användes i arbetet, dels för att skapa en ortomosaik från flygfoton men även för att utföra en bildnormalisering. GIS programvaran ArcGIS Pro tillhandahåller flera algoritmer för klassificering av raster. Algoritmerna SVM och RT, viktades mot varandra och SVM användes vidare i metoden. Med olika generaliserings-verktyg kunde strömhabitat identifieras och förstärkas. Även olika terrängmodeller skapades från flygfoton och Lantmäteriets nationella höjdmodell. Dessa granskades mot varandra utifrån olika aspekter som variationer i bland annat detaljrikedom, generaliseringsgrad och återspeglandet av vattenytan.  Slutsatsen av studien är att klassificering av strömhabitat kan göras i ett GIS-program med en lägesosäkerhet på mellan 25 och 40 %, beroende på vilka strömhabitat som ska klassificeras. Efter utrivningen uppstod 17 zoner med förändrade strömhabitat vilket var två mer än vad prognoser förutsatt. Vidare påverkades vattenvolymen markant då en minskning på ca 40 % skedde från 2018 till 2020. En areal av ca 1,5 hektar berördes då gammal älvbotten blev torrlagd i samband med dammutrivningen. Ett samband syntes mellan avståndet från kraftverket och torrlagd botten då dessa ytor sågs minska i storlek i takt med att avståndet ökade. Att undersöka vart vattennivån påverkats som mest var inte möjligt i brist på data. Studien har utvecklat en metod att analysera en dammutrivnings påverkan på ett vattendrag med data från UAV och bottenskanning.

Dans ce travail, nous nous sommes intéressés à l'étude asymptotique d'objets combinatoires aléatoires. Deux thèmes ont particulièrement retenu notre attention : les cartes planaires aléatoires et les modèles combinatoires liés à la théorie des fragmentations. La théorie mathématique des cartes planaires aléatoires est née à l'aube de notre millénaire avec les travaux pionniers de Benjamini & Schramm, Angel & Schramm et Chassaing & Schaeffer. Elle a ensuite beaucoup progressé, mais à l'heure où ces lignes sont écrites, de nombreux problèmes fondamentaux restent ouverts. Résumons en quelques mots clés nos principales contributions dans le domaine : l'introduction et l'étude du cactus brownien (avec J.F. Le Gall et G. Miermont), l'étude de la quadrangulation infinie uniforme vue de l'infini (avec L. Ménard et G. Miermont), ainsi que des travaux plus théoriques sur les graphes aléatoires stationnaires d'une part et les graphes empilables dans $\R^d$ d'autre part (avec I. Benjamini). La théorie des fragmentations est beaucoup plus ancienne et remonte à des travaux de Kolmogorov (1941) et de Filippov (1961). Elle est maintenant bien développée (voir par exemple l'excellent livre de J. Bertoin), et nous ne nous sommes pas focalisés sur cette théorie mais plutôt sur ses applications à des modèles combinatoires. Elle s'avère en effet très utile pour étudier différents modèles de triangulations récursives du disque (travail effectué avec J.F. Le Gall) et les recherches partielles dans les quadtrees (travail effectué avec A. Joseph). / The subject of this thesis is the asymptotic study of large random combinatorial objects. This is obviously very broad, and we focused particularly on two themes: random planar maps and their limits, and combinatorial models that are in a way linked to fragmentation theory. The mathematical theory of random planar maps is quite young and was triggered by works of Benjamini & Schramm, Angel & Schramm and Chassaing & Schaeffer. This fascinating field is still growing and fundamental problems remain unsolved. We present some new results in both the scaling limit and local limit theories by introducing and studying the Brownian Cactus (with J.F. Le Gall and G. Miermont), giving a new view point, a view from infinity, at the Uniform Infinite Planar Quadrangulation (UIPQ) and bringing more theoretical contributions on stationary random graphs and sphere packable graphs (with I. Benjamini). Fragmentation theory is much older and can be tracked back to Kolmogorov and Filippov. Our goal was not to give a new abstract contribution to this well-developed theory (see the beautiful book of J. Bertoin) but rather to apply it to random combinatorial objects. Indeed, fragmentation theory turned out to be useful in the study of the so-called random recursive triangulations of the disk (joint work with J.F. Le Gall) and partial match queries in random quadtrees (joint work with A. Joseph).