No description available.

Online computation is a model for formulating decision making under uncertainty. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step, the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as robot navigation are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. In this thesis, we first survey three classic online problems, namely the cow-path problem, the Processor-Allocation problem and the Robots-Search-Rays problem and highlight connections between them. Second, the main result is for the One-Robot-Searches-Two-Rays problem for which we consider the weighted scenario, in which the robot is located on a ray with a preferential probability p. We term the One-Robot-Searches-Two-Rays-And-Weighted problem as 1-STRAW (and in general k-STRAW for k searchers). In the 1-STRAW problem, we propose a search strategy which is optimal among weighted geometric states. In addition, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for the 1-STRAW problem. Additionally, we compare our search strategy and its performance with the doubling strategy and the SmartCow algorithm.

Online computation is a model for formulating decision making under uncertainty. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step, the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as robot navigation are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. In this thesis, we first survey three classic online problems, namely the cow-path problem, the Processor-Allocation problem and the Robots-Search-Rays problem and highlight connections between them. Second, the main result is for the One-Robot-Searches-Two-Rays problem for which we consider the weighted scenario, in which the robot is located on a ray with a preferential probability p. We term the One-Robot-Searches-Two-Rays-And-Weighted problem as 1-STRAW (and in general k-STRAW for k searchers). In the 1-STRAW problem, we propose a search strategy which is optimal among weighted geometric states. In addition, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for the 1-STRAW problem. Additionally, we compare our search strategy and its performance with the doubling strategy and the SmartCow algorithm.

Motion planning is an increasingly important field of research. Factory automation is becoming more prevalent and at the same time, production runs are shortening in the name of customisation. With computer controlled equipment becoming cheaper and more modular, setting up near-fully automated production lines is becoming fast and easy. This means that the actual programming of the robots and assembly system is becoming the rate determining step. Automated motion planning is a possible solution to this—but only if it can run fast enough. Many heuristic planners have been created in an attempt to achieve the necessary speeds in off-line (or more ambitiously, on-line) processing. This thesis aims to show that different types of heuristic planners can be designed to take advantage of specialised environments or robot characteristics. To show this, three distinct classes of heuristic planners are put forward for discussion. The first of these classes, addressed in Chapter 2, is of very generic planners which will work in virtually all situations (ie. almost any combination of robot and environment). This generality is obviously useful when lacking more specific domain knowledge. However these methods do suffer performance-wise in comparison with more specialised planners when there are characteristics of the problem which can be targeted. Chapter 3 moves to planners which are designed to specifically address certain peculiarities of the environment. Particular focus is given to environments whose corresponding configuration-spaces contain narrow gaps and passages. Finally Chapter 4 addresses a third class of planners: those which are designed for specific types of robots and movements. The particular focus is on locomotion for legged vehicles. For each of these three classes, some discussion is made of existing planners which can be so characterised. In addition, a novel algorithm is introduced in each as an example for particular consideration.

Searching for objects in physical space is one of the most important tasks for humans. Mobile sensor networks can be great tools for the task. Transient targets refer to a class of objects which are not identifiable unless momentary sensing and signaling conditions are satisfied. The transient property is often introduced by target attributes, privacy concerns, environment constraints, and sensing limitations. Transient target localization problems are challenging because the transient property is often coupled with factors such as sensing range limits, various coverage functions, constrained mobility, signal correspondence, limited number of searchers, and a vast searching region. To tackle these challenge tasks, we gradually increase complexity of the transient target localization problem such as Single Robot Single Target (SRST), Multiple Robots Single Target (MRST), Single Robot Multiple Targets (SRMT) and Multiple Robots Multiple Targets (MRMT). We propose the expected searching time (EST) as a primary metric to assess the searching ability of a single robot and the spatiotemporal probability occupancy grid (SPOG) method that captures transient characteristics of multiple targets and tracks the spatiotemporal posterior probability distribution of the target transmissions. Besides, we introduce a team of multiple robots and develop a sensor fusion model using the signal strength ratio from the paired robots in centralized and decentralized manners. We have implemented and validated the algorithms under a hardware-driven simulation and physical experiments.

Assistive mobile robots, such as intelligent wheelchairs, that can navigate autonomously in response to high level commands from a user can greatly benefit people with cognitive and physical disabilities by increasing their mobility. In this work, we address the problem of safe, comfortable, and customizable motion planning of such assistive mobile robots. We recognize that for an assistive robot to be acceptable to human users, its motion should be safe and comfortable. Further, different users should be able to customize the motion according to their comfort. We formalize the notion of motion comfort as a discomfort measure that can be minimized to compute comfortable trajectories, and identify several properties that a trajectory must have for the motion to be comfortable. We develop a motion planning framework for planning safe, comfortable, and customizable trajectories in small-scale space. This framework removes the limitations of existing methods for planning motion of a wheeled mobile robot moving on a plane, none of which can compute trajectories with all the properties necessary for comfort. We formulate a discomfort cost functional as a weighted sum of total travel time, time integral of squared tangential jerk, and time integral of squared normal jerk. We then define the problem of safe and comfortable motion planning as that of minimizing this discomfort such that the trajectories satisfy boundary conditions on configuration and its higher derivatives, avoid obstacles, and satisfy constraints on curvature, speed, and acceleration. This description is transformed into a precise mathematical problem statement using a general nonlinear constrained optimization approach. The main idea is to formulate a well-posed infinite-dimensional optimization problem and use a conforming finite-element discretization to transform it into a finite-dimensional problem for a numerical solution. We also outline a method by which a user may customize the motion and present some guidelines for conducting human user studies to validate or refine the discomfort measure presented in this work. Results show that our framework is capable of reliably planning trajectories that have all the properties necessary for comfort. We believe that our work is an important first step in developing autonomous assistive robots that are acceptable to human users. / text

This diploma project is focused on possible applications of computational geometry methods for robot motion planning among static and dynamic obstacles, particularly based on global robot motion planning by means of generalised Voronoi diagrams. The main effort was to convert this complex geometric and analytic problem to graph theory environment where the tasks of planning and searching paths between pairs of the graph vertices are effeciently solvable. The Voronoi diagram is created considering the whole searching space, while edges of this diagram satisfy that the distance from the surrounding obstacles is maximised and the path found along the Voronoi diagram edges is optimised from the point of view of its security (and it is collision-free).

L’audition est une modalité utile pour aider un robot à explorer et comprendre son environnement sonore. Dans cette thèse, nous nous intéressons à la tâche de localiser une ou plusieurs sources sonores mobiles et intermittentes à l’aide d’un robot mobile équipé d’une antenne de microphones en exploitant la mobilité du robot pour améliorer la localisation. Nous proposons d’abord un modèle bayésien pour localiser une seule source mobile intermittente. Ce modèle estime conjointement la position et l’activité de la source au cours du temps et s’applique à tout type d’antenne. Grâce au mouvement du robot, il peut estimer la distance de la source et résoudre l’ambiguïté avant-arrière qui apparaît dans le cas des antennes linéaires. Nous proposons deux implémentations de ce modèle, l’une à l’aide d’un filtre de Kalman étendu basé sur des mélanges de gaussiennes et l’autre à l’aide d’un filtre à particules, que nous comparons en termes de performance et de temps de calcul. Nous étendons ensuite notre modèle à plusieurs sources intermittentes et mobiles. En combinant notre filtre avec un joint probability data association filter (JPDAF), nous pouvons estimer conjointement les positions et activités de deux sources sonores dans un environnement réverbérant. Enfin nous faisons une contribution à la planification de mouvement pour réduire l’incertitude sur la localisation d’une source sonore. Nous définissons une fonction de coût avec l’alternative entre deux critères: l’entropie de Shannon ou l’écart-type sur l’estimation de la position. Ces deux critères sont intégrés dans le temps avec un facteur d’actualisation. Nous adaptons alors l’algorithme de Monte-Carlo tree search (MCTS) pour trouver, efficacement, le mouvement du robot qui minimise notre fonction de coût. Nos expériences montrent que notre méthode surpasse, sur le long terme, d’autres méthodes de planification pour l’audition robotique / Robot audition provides hearing capability for robots and helps them explore and understand their sound environment. In this thesis, we focus on the task of sound source localization for a single or multiple, intermittent, possibly moving sources using a mobile robot and exploiting robot motion to improve the source localization. We propose a Bayesian filtering framework to localize the position of a single, intermittent, possibly moving sound source. This framework jointly estimates the source location and its activity over time and is applicable to any micro- phone array geometry. Thanks to the movement of the robot, it can estimate the distance to the source and solve the front-back ambiguity which appears in the case of a linear microphone array. We propose two implementations of this framework based on an extended mixture Kalman filter (MKF) and on a particle filter, that we compare in terms of performance and computation time. We then extend our model to the context of multiple, intermittent, possibly moving sources. By implementing an extended MKF with joint probabilistic data association filter (JPDAF), we can jointly estimate the locations of two sources and their activities over time. Lastly, we make a contribution on long-term robot motion planning to optimally reduce the uncertainty in the source location. We define a cost function with two alternative criteria: the Shannon entropy or the standard deviation of the estimated belief. These entropies or standard deviations are integrated over time with a discount factor. We adapt the Monte Carlo tree search (MCTS) method for efficiently finding the optimal robot motion that will minimize the above cost function. Experiments show that the proposed method outperforms other robot motion planning methods for robot audition in the long run