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.

Laser welding is used in modern industrial production due to its high welding speed and good welding performance comparing to more traditional arc welding. To improve the flex-ibility, robots can be used to mount the laser tool. However, laser welding has a high require-ment for the accuracy in positioning the laser tool. There are three main related variables which affect the laser welding accuracy: robot path accuracy, workpiece geometry and fixture repeatability. Thus, joint tracking is very important for laser welding to achieve high quality welds. There are many joint tracking systems which were proposed in recent years. After receiv-ing the joint information, a control system is necessary to control the robot motion in real-time. The open control system for the industrial robot is one trend for the future. A lot of methods and systems are proposed to control the robot motion. Some systems can achieve a high accuracy in the experiments. However, it is still hard to apply them in practical indus-trial production. Thus more commercial solutions appear to overcome the robot motion problem nowadays. They are very useful to realize practical applications. ABB EGM path correction module, a new function of Robotware, is one of the com-mercial solutions for robot motion control in real time. In the experiments presented in this work, a computer is used to simulate a sensor to create a path correction signal. To test its feasibility for the laser welding application, many experiments are conducted. One was to test the robot path repeatability when there is no correction message sent to the robot. Another was to test the level of accuracy EGM can achieve during the correction process. Different types of paths and three different speeds were separately carried out. The results showed that it is possible to use the EGM in the laser welding application. In the EGM feasibility test, there exists deviation in the z-direction. Since these deviations are less than 0.2mm, it will have a minor influence the laser welding performance, implying that the EGM path correction can be applied in practical production.

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.

Robot motion can be described in several alternative representations, including joint configuration or end-effector spaces. These representations are often used for manipulation or navigation tasks but they are not suitable for tasks that involve close interaction with the environment. In these scenarios, collisions and relative poses of the robot and its surroundings create a complex planning space. To deal with this complexity, we exploit several representations that capture the state of the interaction, rather than the state of the robot. Borrowing notions of topology invariances and homotopy classes, we design task spaces based on winding numbers and writhe for synthesizing winding motion, and electro-static fields for planning reaching and grasping motion. Our experiments show that these representations capture the motion, preserving its qualitative properties, while generalising over finer geometrical detail. Based on the same motivation, we utilise a scale and rotation invariant representation for locally preserving distances, called interaction mesh. The interaction mesh allows for transferring motion between robots of different scales (motion re-targeting), between humans and robots (teleoperation) and between different environments (motion adaptation). To estimate the state of the environment we employ real-time sensing techniques utilizing dense stereo tracking, magnetic tracking sensors and inertia measurements units. We combine and exploit these representations for synthesis and generalization of motion in dynamic environments. The benefit of this method is on problems where direct planning in joint space is extremely hard whereas local optimal control exploiting topology and metric of these novel representations can efficiently compute optimal trajectories. We formulate this approach in the framework of optimal control as an approximate inference problem. This allows for consistent combination of multiple task spaces (e.g. end-effector, joint space and the abstract task spaces we investigate in this thesis). Motion generalization to novel situations and kinematics is similarly performed by projecting motion from abstract representations to joint configuration space. This technique, based on operational space control, allows us to adapt the motion in real time. This process of real-time re-mapping generates robust motion, thus reducing the amount of re-planning. We have implemented our approach as a part of an open source project called the Extensible Optimisation library (EXOTica). This software allows for defining motion synthesis problems by combining task representations and presenting this problem to various motion planners using a common interface. Using EXOTica, we perform comparisons between different representations and different planners to validate that these representations truly improve the motion planning.

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).

Diploma thesis is focused on the solution of synchronization of the robot motion with a moving conveyor belt. It informs about basic principles and possibilities of using similar applications. It describes individual elements used in the application, their importance and function. It provides an overview of proposed program codes for the programmable logic controller, the smart camera and the robot. The result is the creation of a functional illustrative application with KUKA robot.