Dissertations / Theses on the topic 'Sampling-based motion planning'

Automatically planning the motion of rigid bodies moving in 3D by translation and rotation in the presence of obstacles has long been a research challenge for mathematicians, algorithm designers and roboticists. The field made dramatic progress with the introduction of the probabilistic and sampling-based "roadmap" approach. However, motion planning when narrow passages are present has remained a challenge. This thesis presents a framework for experimenting with combinations of sampling strategies and local planners, and for comparing their performance on user defined input problems. Our framework also allows parallel implementations on a variable number of processing cores. We present experimental results. In particular, our framework has allowed us to find combinations of sampling strategy choice with local planner choice that can solve difficult benchmark motion planningproblems.<br>La planification automatique du mouvement de corps rigides en mouvement 3D par translation et rotation en présence d'obstacles a longtemps été un défi pour la recherche pour les mathématiciens, les concepteurs de l'algorithme et roboticiens. Le champ a fait d'importants progrès avec l'introduction de la méthode de "feuille de route" probabiliste basée sur l'échantillonnage. Mais la planification du mouvement en présence de passages étroits est resté un défi.Cette thése présente un cadre d'expérimentation avec des combinaisons de stratégies d'échantillonnage et les planificateurs locaux, et de comparaison de leurs performances sur des problémes définis par l'utilisateur. Notre programme peut également être exécuté parallèle sur un nombre variable de processeurs. Nous présentons des résultats expérimentaux. En particulier, notre cadre nous a permis de trouver des combinaisons de choix d'une stratégie d'échantillonnage avec choix de planificateur local qui peut résoudre des problèmes difficiles de référence.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2014.<br>CD-ROM has video of vehicle.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 223-237).<br>While navigating, autonomous vehicles often must overcome significant uncertainty in their understanding of the world around them. Real-world environments may be cluttered and highly dynamic, with uncertainty in both the current state and future evolution of environmental constraints. The vehicle may also face uncertainty in its own motion. To provide safe navigation under such conditions, motion planning algorithms must be able to rapidly generate smooth, certifiably robust trajectories in real-time. The primary contribution of this thesis is the development of a real-time motion planning framework capable of generating feasible paths for autonomous vehicles in complex environments, with robustness guarantees under both internal and external uncertainty. By leveraging the trajectory-wise constraint checking of sampling-based algorithms, and in particular rapidly-exploring random trees (RRT), the proposed algorithms can efficiently evaluate and enforce complex robustness conditions. For linear systems under bounded uncertainty, a sampling-based motion planner is presented which iteratively tightens constraints in order to guarantee safety for all feasible uncertainty realizations. The proposed bounded-uncertainty RRT* (BURRT*) algorithm scales favorably with environment complexity. Additionally, by building upon RRT*, BU-RRT* is shown to be asymptotically optimal, enabling it to efficiently generate and optimize robust, dynamically feasible trajectories. For large and/or unbounded uncertainties, probabilistically feasible planning is provided through the proposed chance-constrained RRT (CC-RRT) algorithm. Paths generated by CC-RRT are guaranteed probabilistically feasible for linear systems under Gaussian uncertainty, with extensions considered for nonlinear dynamics, output models, and/or non-Gaussian uncertainty. Probabilistic constraint satisfaction is represented in terms of chance constraints, extending existing approaches by considering both internal and external uncertainty, subject to time-step-wise and path-wise feasibility constraints. An explicit bound on the total risk of constraint violation is developed which can be efficiently evaluated online for each trajectory. The proposed CC-RRT* algorithm extends this approach to provide asymptotic optimality guarantees; an admissible risk-based objective uses the risk bounds to incentivize risk-averse trajectories. Applications of this framework are shown for several motion planning domains, including parafoil terminal guidance and urban navigation, where the system is subject to challenging environmental and uncertainty characterizations. Hardware results demonstrate a mobile robot utilizing this framework to safely avoid dynamic obstacles.<br>by Brandon Luders.<br>Ph. D.

One of the main focus of robotics is to integraterobotic tasks and motion planning, which has an increasedsignificance due to their growing number of application fieldsin transportation, navigation, warehouse management and muchmore. A crucial step towards this direction is to have robotsautomatically plan its trajectory to accomplish the given task.In this project a multi-layered approach was implemented toaccomplish it. Our framework consists of a discrete high-levelplanning layer that is designed for planning, and a continuouslow-level search layer that uses a sampling-based method for thetrajectory searching. The layers will interact with each otherduring the search for a solution. In order to coordinate formulti-agent system, velocity tuning is used to avoid collisions, anddifferent priority are assigned to each robot to avoid deadlocks.As a result, the framework trades off completeness for efficiency.The main aim of this project is to study and learn about high-level motion planning and multi-agent system, as an introductionto robotics and computer science.<br>En viktig aspekt inom robotik är att integrera robotuppgifter med rörelseplanering, som har en ökande be- tydelse för samhället på grund av dess applikationsområde inom t.ex. transport, navigering och lagerhantering. Ett avgörande steg till detta är att få robotarna automatiskt planerar sin bana för att utföra de givna uppgifterna. I detta projekt implementerades “Multi-layered” metod för att uppnå detta. Metoden består av ett hög-nivå diskret planeringslager som är designad för planering, och ett kontinuerligt låg-nivå sökningslager som använder ”sampling-based” algoritmer för sökning av bana. Lagerna interageras med varandra under den tiden där metoden söker efter en önskvärd bana som satisfiera uppdraget. För att koordinera samtliga robotar används den frikopplat approachen där hastigheter för olika robotar justeras till att undvika kollisioner, samt olika prioriteringar tilldelas för varje robot för att undvika ett blockerat låsläge. ”Sampling-based” algoritmer och den frikopplat approachen är oftast mer effektivt tidsmässigt men garantera inte att lösning kommer att hittas även om den existerar. Syftet med detta projekt är att studera och lära sig om rörelseplanering på högt-nivå och multi-agentsystem, som en introduktion till robotik och datavetenskap.<br>Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

Robot motion planning is one of the central problems in robotics, and has received considerable amount of attention not only from roboticists but also from the control and artificial intelligence (AI) communities. Despite the different types of applications and physical properties of robotic systems, many high-level tasks of autonomous systems can be decomposed into subtasks which require point-to-point navigation while avoiding infeasible regions due to the obstacles in the workspace. This dissertation aims at developing a new class of sampling-based motion planning algorithms that are fast, efficient and asymptotically optimal by employing ideas from Machine Learning (ML) and Dynamic Programming (DP). First, we interpret the robot motion planning problem as a form of a machine learning problem since the underlying search space is not known a priori, and utilize random geometric graphs to compute consistent discretizations of the underlying continuous search space. Then, we integrate existing DP algorithms and ML algorithms to the framework of sampling-based algorithms for better exploitation and exploration, respectively. We introduce a novel sampling-based algorithm, called RRT#, that improves upon the well-known RRT* algorithm by leveraging value and policy iteration methods as new information is collected. The proposed algorithms yield provable guarantees on correctness, completeness and asymptotic optimality. We also develop an adaptive sampling strategy by considering exploration as a classification (or regression) problem, and use online machine learning algorithms to learn the relevant region of a query, i.e., the region that contains the optimal solution, without significant computational overhead. We then extend the application of sampling-based algorithms to a class of stochastic optimal control problems and problems with differential constraints. Specifically, we introduce the Path Integral - RRT algorithm, for solving optimal control of stochastic systems and the CL-RRT# algorithm that uses closed-loop prediction for trajectory generation for differential systems. One of the key benefits of CL-RRT# is that for many systems, given a low-level tracking controller, it is easier to handle differential constraints, so complex steering procedures are not needed, unlike most existing kinodynamic sampling-based algorithms. Implementation results of sampling-based planners for route planning of a full-scale autonomous helicopter under the Autonomous Aerial Cargo/Utility System Program (AACUS) program are provided.

Thesis (MScEng)--Stellenbosch University, 2013.<br>ENGLISH ABSTRACT: In order to navigate dynamic, cluttered environments safely, fully autonomous Unmanned Aerial Vehicles (UAVs) are required to plan conflict-free trajectories between two states in position-time space efficiently and reliably. Kinodynamic planning for vehicles with non-holonomic dynamic constraints is an NP-hard problem which is usually addressed using sampling-based, probabilistically complete motion planning algorithms. These algorithms are often applied in conjunction with a finite set of simple geometric motion primitives which encapsulate the dynamic constraints of the vehicle. This ensures that composite trajectories generated by the planning algorithm adhere to the vehicle dynamics. For many vehicles, accurate tracking of position-based trajectories is a non-trivial problem which demands complicated control techniques with high energy requirements. In an effort to reduce control complexity and thus also energy consumption, a generic Local Planning Method (LPM), able to plan trajectories based on implicitly-defined motion primitives, is developed in this project. This allows the planning algorithm to construct trajectories which are based on simulated results of vehicle motion under the control of a rudimentary auto-pilot, as opposed to a more complicated position-tracking system. The LPM abstracts motion primitives in such a way that it may theoretically be made applicable to various vehicles and control systems through simple substitution of the motion primitive set. The LPM, which is based on a variation of the Levenberg-Marquardt Algorithm (LMA), is integrated into a well-known Probabilistic Roadmap (PRM) kinodynamic planning algorithm which is known to work well in dynamic and cluttered environments. The complete motion planning algorithm is tested thoroughly in various simulated environments, using a vehicle model and controllers which have been previously verified against a real UAV during practical flight tests.<br>AFRIKAANSE OPSOMMING: Ten einde dinamiese, voorwerpryke omgewings veilig te navigeer, word daar vereis dat volledig-outonome onbemande lugvoertuie konflikvrye trajekte tussen twee posisie-tydtoestande doeltreffend en betroubaar kan beplan. Kinodinamiese beplanning is ’n NPmoeilike probleem wat gewoonlik deur middel van probabilisties-volledige beplanningsalgoritmes aangespreek word . Hierdie algoritmes word dikwels in kombinasie met ’n eindige stel eenvoudige geometriese maneuvers, wat die dinamiese beperkings van die voertuig omvat, ingespan. Sodanig word daar verseker dat trajekte wat deur die beplaningsalgoritme saamgestel is aan die dinamiese beperkings van die voertuig voldoen. Vir baie voertuie, is die akkurate volging van posisie-gebaseerde trajekte ’n nie-triviale probleem wat die gebruik van ingewikkelde, energie-intensiewe beheertegnieke vereis. In ’n poging om beheer-kompleksiteit, en dus energie-verbruik, te verminder, word ’n generiese plaaslike-beplanner voorgestel. Hierdie algoritme stel die groter kinodinamiese beplanner in staat daartoe om trajekte saam te stel wat op empiriese waarnemings van voertuig-trajekte gebaseer is. ’n Eenvoudige beheerstelsel kan dus gebruik word, in teenstelling met die meer ingewikkelde padvolgingsbeheerders wat benodig word om eenvoudige geometriese trajekte akkuraat te volg. Die plaaslike-beplanner abstraeer maneuvers in so ’n mate dat dit teoreties op verskeie voertuie en beheerstelsels van toepassing gemaak kan word deur eenvoudig die maneuver-stel te vervang. Die plaaslike-beplanner, wat afgelei is van die Levenberg-Marquardt-Algoritme (LMA), word in ’n welbekende “Probabilistic Roadmap” (PRM) kinodinamiese-beplanningsalgoritme geïntegreer. Dit word algemeen aanvaar dat die PRM effektief werk in dinamiese, voorwerpryke omgewings. Die volledige beplanningsalgoritme word deeglik in verskeie, gesimuleerde omgewings getoets op ’n voertuig-model en -beheerders wat voorheen vir akkuraatheid teenoor ’n werklike voertuig gekontroleer is tydens praktiese vlugtoetse.

An urban operation of unmanned aerial vehicles (UAVs) demands a high level of autonomy for tasks presented in a cluttered environment. While fixed-wing UAVs are well suited for long-endurance missions at a high altitude, enabling them to navigate inside an urban area brings another level of challenges. Their inability to hover and low agility in motion cause more difficulties on finding a feasible path to move safely in a compact region, and the limited payload allows only low-grade sensors for state estimation and control. We address the problem of achieving vision-based autonomous navigation for a small fixed-wing in an urban area with contributions to the following several key topics. Firstly, for robust attitude estimation during dynamic maneuvering, we take advantage of the line regularity in an urban scene, which features vertical and horizontal edges of man-made structures. The sensor fusion with gravity-related line segments and gyroscopes in a Kalman filter can provide driftless and realtime attitude for ight stabilization. Secondly, as a prerequisite to sensor fusion, we present a convenient self-calibration scheme based on the factorization method. Natural references such as gravity, vertical edges, and distant scene points, available in urban fields, are sufficient to find intrinsic and extrinsic parameters of inertial and vision sensors. Lastly, to generate a dynamically feasible motion plan, we propose a discrete planning method that encodes a path into interconnections of finite trim states, which allow a significant dimension reduction of a search space and result in naturally implementable paths integrated with ight controllers. The most probable path to reach a target is computed by the Markov Decision Process with motion uncertainty due to wind, and a minimum target observation time is imposed on the final motion plan to consider a camera's limited field-of-view. In this thesis, the effectiveness of our vision-based navigation system is demonstrated by what we call an "air slalom" task in which the UAV must autonomously search and localize multiple gates, and pass through them sequentially. Experiment results with a 1m wing-span airplane show essential navigation capabilities demanded in urban operations such as maneuvering passageways between buildings.

This paper deals with the problem of object path planning in 3D space. The goal is to create program which allows users to create a scene used for path planning, perform the planning and finally visualize path in the scene. Work is focused on probabilistic algorithms that are described in the theoretical part. The practical part describes the design and implementation of application. Finally, several experiments are performed to compare the performance of different algorithms and demonstrate the functionality of the program.

Research about unmanned ground vehicles (UGVs) has received an increased amount of attention in recent years, partly due to the many applications of UGVs in areas where it is inconvenient or impossible to have human operators, such as in mines or urban search and rescue. Two closely linked problems that arise when developing such vehicles are motion planning and control of the UGV. This thesis explores these subjects for a UGV with an unknown, and possibly time-variant, dynamical model. A framework is developed that includes three components: a machine learning algorithm to estimate the unknown dynamical model of the UGV, a motion planner that plans a feasible path for the vehicle and a controller making the UGV follow the planned path. The motion planner used in the framework is a lattice-based planner based on input sampling. It uses a dynamical model of the UGV together with motion primitives, defined as a sequence of states and control signals, which are concatenated online in order to plan a feasible path between states. Furthermore, the controller that makes the vehicle follow this path is a model predictive control (MPC) controller, capable of taking the time-varying dynamics of the UGV into account as well as imposing constraints on the states and control signals. Since the dynamical model is unknown, the machine learning algorithm Bayesian linear regression (BLR) is used to continuously estimate the model parameters online during a run. The parameter estimates are then used by the MPC controller and the motion planner in order to improve the performance of the UGV. The performance of the proposed motion planning and control framework is evaluated by conducting a series of experiments in a simulation study. Two different simulation environments, containing obstacles, are used in the framework to simulate the UGV, where the performance measures considered are the deviation from the planned path, the average velocity of the UGV and the time to plan the path. The simulations are either performed with a time-invariant model, or a model where the parameters change during the run. The results show that the performance is improved when combining the motion planner and the MPC controller with the estimated model parameters from the BLR algorithm. With an improved model, the vehicle is capable of maintaining a higher average velocity, meaning that the plan can be executed faster. Furthermore, it can also track the path more precisely compared to when using a less accurate model, which is crucial in an environment with many obstacles. Finally, the use of the BLR algorithm to continuously estimate the model parameters allows the vehicle to adapt to changes in its model. This makes it possible for the UGV to stay operational in cases of, e.g., actuator malfunctions.

In this thesis we modified a sampling-based motion planning algorithm to improve sampling efficiency. First, we modify the RRT* motion planning algorithm with a local motion planner that guarantees collision-free state trajectories without explicitly checking for collision with obstacles. The control trajectories are generated by solving a sequence of quadratic programs with Control Barrier Functions (CBF) constraints. If the control trajectories satisfy the CBF constraints, the state trajectories are guaranteed to stay in the free subset of the state space. Second, we use a stochastic optimization algorithm to adapt the sampling density function of RRT* to increase the probability of sampling in promising regions in the configuration space. In our approach, we use the nonparametric generalized cross-entropy (GCE) method is used for importance sampling, where a subset of the sampled RRT* trajectories is incrementally exploited to adapt the density function. The modified algorithms, the Adaptive CBF-RRT* and the CBF-RRT*, are demonstrated with numerical examples using the unicycle dynamics. The Adaptive CBF-RRT* has been shown to yield paths with lower cost with fewer tree vertexes than the CBF-RRT*.<br>2022-03-27T00:00:00Z

The motion planning problem can be formulated as a Markov decision process (MDP), if the uncertainties in the robot motion and environments can be modeled probabilistically. The complexity of solving these MDPs grow exponentially as the dimension of the problem increases and hence, it is nearly impossible to solve the problem even without constraints. Using hierarchical methods, these MDPs can be transformed into a semi-Markov decision process (SMDP) which only needs to be solved at certain landmark states. In the deterministic robotics motion planning community, sampling based algorithms like probabilistic roadmaps (PRM) and rapidly exploring random trees (RRTs) have been successful in solving very high dimensional deterministic problem. However they are not robust to system with uncertainties in the system dynamics and hence, one of the primary objective of this work is to generalize PRM/RRT to solve motion planning with uncertainty. We first present generalizations of randomized sampling based algorithms PRM and RRT, to incorporate the process uncertainty, and obstacle location uncertainty, termed as "generalized PRM" (GPRM) and "generalized RRT" (GRRT). The controllers used at the lower level of these planners are feedback controllers which ensure convergence of trajectories while mitigating the effects of process uncertainty. The results indicate that the algorithms solve the motion planning problem for a single agent in continuous state/control spaces in the presence of process uncertainty, and constraints such as obstacles and other state/input constraints. Secondly, a novel adaptive sampling technique, termed as "adaptive GPRM" (AGPRM), is proposed for these generalized planners to increase the efficiency and overall success probability of these planners. It was implemented on high-dimensional robot n-link manipulators, with up to 8 links, i.e. in a 16-dimensional state-space. The results demonstrate the ability of the proposed algorithm to handle the motion planning problem for highly non-linear systems in very high-dimensional state space. Finally, a solution methodology, termed the "multi-agent AGPRM" (MAGPRM), is proposed to solve the multi-agent motion planning problem under uncertainty. The technique uses a existing solution technique to the multiple traveling salesman problem (MTSP) in conjunction with GPRM. For real-time implementation, an ?inter-agent collision detection and avoidance? module was designed which ensures that no two agents collide at any time-step. Algorithm was tested on teams of homogeneous and heterogeneous agents in cluttered obstacle space and the algorithm demonstrate the ability to handle such problems in continuous state/control spaces in presence of process uncertainty.

Robots already impact the way we understand our world and live our lives. However, their impact and use is limited by the skills they possess. Currently deployed autonomous robots lack the manipulation skills possessed by humans. To achieve general autonomy and applicability in the real world, robots must possess such skills. Autonomous manipulation requires algorithms that rapidly and reliably compute collision-free motion for robotic limbs with many degrees of freedom. Unfortunately, adequate algorithms for this task do not currently exist. Though there are many dimensions of the real-world planning task that require further research. A central problem of reliable real-world planning is that planners must rely on incomplete and inaccurate information about the world in which they are planning. The motion planning problem has exponential complexity in the robot's degrees of freedom. Consequently, the most successful planning algorithms use incomplete information obtained via sampling a subset of all possible movements. Additionally, real-world robots generally obtain information about the state of their environment through lasers, cameras and other sensors. The information obtained from these sensors contains noise and error. Thus the planner's incomplete information about the world is possibly inaccurate as well. Despite such limited information, a planner must be capable of quickly generating collision free motions to facilitate general purpose autonomous robots. This thesis proposes a new utility-guided framework for motion planning that can reliably compute collision-free motions with the efficiency required for real-world planning. The utility-guided approach begins with the observation there is regularity in space of possible motions available to a robot. Further, certain motions are more crucial than others for computing collision free paths. Together these observations form structure in the robot's space of possible movements. This structure provides a guide for the planner's exploration of possible motions. Because a complete understanding of this structure is computationally intractable, the utility-guided framework incrementally develops an approximate model discovered by past exploration. This model of the structure is used to select explorations that maximally benefit the planner. Information provided by each exploration improves the planner's approximation. The process of incremental improvement and further guided exploration iterates until an adequate model of configuration space is constructed. Discovering and exploiting structure in a robot's configuration space enables a utility-guided planner to achieve the performance and reliability required by real-world motion planning. This thesis describes applications of the utility-guided motion-planning framework to multi-query sampling-based roadmap and random-tree motion planning. Additionally, the utility-guided framework is extended to develop a planner that can successfully plan despite inaccuracies in its perception of the environment and to guide further sensing to reduce uncertainty and maximally improve the utility of the path.

Control of complex systems satisfying rich temporal specification has become an increasingly important research area in fields such as robotics, control, automotive, and manufacturing. Popular specification languages include temporal logics, such as Linear Temporal Logic (LTL) and Computational Tree Logic (CTL), which extend propositional logic to capture the temporal sequencing of system properties. The focus of this dissertation is on the control of high-dimensional systems and on timed specifications that impose explicit time bounds on the satisfaction of tasks. This work proposes and evaluates methods and algorithms for synthesizing provably correct control policies that deal with the scalability problems. Ideas and tools from formal verification, graph theory, and incremental computing are used to synthesize satisfying control strategies. Finite abstractions of the systems are generated, and then composed with automata encoding the specifications. The first part of this dissertation introduces a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The specification has two parts: (1) a global specification given as an LTL formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula, and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The second part of the dissertation focuses on stochastic systems with temporal and uncertainty constraints. A specification language called Gaussian Distribution Temporal Logic is introduced as an extension of Boolean logic that incorporates temporal evolution and noise mitigation directly into the task specifications. A sampling-based algorithm to synthesize control policies is presented that generates a transition system in the belief space and uses local feedback controllers to break the curse of history associated with belief space planning. Switching control policies are then computed using a product Markov Decision Process between the transition system and the Rabin automaton encoding the specification.The approach is evaluated in experiments using a camera network and ground robot. The third part of this dissertation focuses on control of multi-vehicle systems with timed specifications and charging constraints. A rich expressivity language called Time Window Temporal Logic (TWTL) that describes time bounded specifications is introduced. The temporal relaxation of TWTL formulae with respect to the deadlines of tasks is also discussed. The key ingredient of the solution is an algorithm to translate a TWTL formula to an annotated finite state automaton that encodes all possible temporal relaxations of the given formula. The annotated automata are composed with transition systems encoding the motion of all vehicles, and with charging models to produce control strategies for all vehicles such that the overall system satisfies the mission specification. The methods are evaluated in simulation and experimental trials with quadrotors and charging stations.

碩士<br>國立臺灣大學<br>電機工程學研究所<br>104<br>In the present work, an socially aware autonomous navigation framework and motion planning algorithm for indoor service robot are proposed. The entirety of our work is based on Robot Operating System (ROS), which serves as the Linux-based middle-ware on which all robotics applications execute and communicate with each other based on an unified formats of messages, and allows sharing of information within a cluster of devices. Within ROS, our navigational framework consists of integrating layered planning scheme, layered costmap update (a ROS concept based on [2]), mapping and localization, as well as base control into a viable navigation system. The social aware functionality is implemented via an establishment of dynamic costmap registering the proxemics of each perceived individual by the robot’s onboard Laser Scan as well as RGB-D sensors. With the aid of sensorial fusion perception of humans within highly dynamic configuration space poses high demand for more agile and flexible motion planning algorithms as well as faster people tracking techniques to ensure safer interaction. For such purpose, this work presents a novel biased sampling-based planning approach which displays both the Anytime Dynamic planning characteristics of search-based path planning algorithms with the computational simplicity of single-query sampling-based approach. We evaluate our motion planning algorithm with 3 major benchmarks: one simulated environment and two real-world scenarios involving partially explored and fully explored maps of the same maze-like indoor space. We compare our proposed algorithm ADRRT* with several major search-based and sampling-based algorithms in terms of the spent cost and computation time on each iteration. And on average, our algorithm not only consumes cost which ranges 8.5% to 16.7% less than its counterparts, but also occupies les than comvi pared to as much as 58.17% to RRT and 95% to RRT* in non-convex environement such as Room 302 of our laboratory. While our technique proves to yield faster and less costly trajectories, the layered costmaps should also be effectively updated to ensure the collision avoidance both with static obstacles as well as people at the robot’s surroundings on a real-time basis. The dynamic costmap layers registers the perceived people’s poses in terms of Gaussian pose estimate, representing the proxemics of each individual. With the notion of proxemics, the navigation framework respects the personal space of others and maneuver according to social norms, an important feature to regulate robotic behavior in order to integrate robots into our society. Such study also serves as springboard toward future works related not limited to human-robot-interaction, multi-robot exploration, and further integration of robotics with the Internet of Things (IoT) framework.

abstract: In this thesis, a new approach to learning-based planning is presented where critical regions of an environment with low probability measure are learned from a given set of motion plans. Critical regions are learned using convolutional neural networks (CNN) to improve sampling processes for motion planning (MP). In addition to an identification network, a new sampling-based motion planner, Learn and Link, is introduced. This planner leverages critical regions to overcome the limitations of uniform sampling while still maintaining guarantees of correctness inherent to sampling-based algorithms. Learn and Link is evaluated against planners from the Open Motion Planning Library (OMPL) on an extensive suite of challenging navigation planning problems. This work shows that critical areas of an environment are learnable, and can be used by Learn and Link to solve MP problems with far less planning time than existing sampling-based planners.<br>Dissertation/Thesis<br>Masters Thesis Computer Science 2019