Improvements in robot autonomy are changing human-robot interaction from low-level manipulation to high-level task-based collaboration. When a robot can independently and autonomously executes tasks, a human in a human-robot team acts as a collaborator or task supervisor instead of a tele-operator. When applying this to planning paths for a robot's motion, it is very important that the supervisor's qualitative intent is translated into aquantitative model so that the robot can produce a desirable consequence. In robotic path planning, algorithms can transform a human's qualitative requirement into a robot's quantitative model so that the robot behavior satisfies the human's intent. In particular, algorithms can be created that allow a human to express multi-objective and topological preferences, and can be built to use verbal communication. This dissertation presents a series of robot motion-planning algorithms, each of which is designed to support some aspect of a human's intent. Specifically, we present algorithms for the following problems: planning with a human-motion constraint, planning with a topological requirement, planning with multiple objectives, and creating models of constraints, requirements, and objectives from verbal instructions. These algorithms create a set of robot behaviors that support flexible decision-making over a range of complex path-planning tasks.

Engineering activities by nature are collaborative endeavors. Single-user applications like CAD, CAE, and CAM force a strictly serial design process, which ultimately lengthens time to market. New multi-user applications such as NXConnect address the issue during the design stage of the product development process by enabling users to work in parallel. Multi-user collaborative tool path planning software addresses the same serial limitations in tool path planning, thereby decreasing cost and increasing the quality of manufacturing processes. As part complexity increases, lead times are magnified by serial workflows. Multi-user tool path planning can shorten the process planning time. But, to be effective, it must be possible to intelligently decompose the manufacturing sequence and distribute path planning assignments among several users. A new method of process decomposition is developed and described in this research. A multi-user CAM (MUCAM) prototype was developed to test the method. The decomposition process and MUCAM prototype together were used to manufacture a part to verify the method.

Free space is represented as a union of (possibly overlapping) generalized cones. An algorithm is presented which efficiently finds good collision free paths for convex polygonal bodies through space littered with obstacle polygons. The paths are good in the sense that the distance of closest approach to an obstacle over the path is usually far from minimal over the class of topologically equivalent collision free paths. The algorithm is based on characterizing the volume swept by a body as it is translated and rotated as a generalized cone and determining under what conditions generalized cone is a subset of another.

We describe a method called Visible Decomposition for computing collision-free paths in real time through a planar environment with a large number of obstacles. This method divides space into local visibility graphs, ensuring that all operations are local. The search time is kept low since the number of regions is proved to be small. We analyze the computational demands of the algorithm and the quality of the paths it produces. In addition, we show test results on a large simulation testbed.

This thesis describes a novel terrain synthesis method based on distances in a weighted graph. The method begins with a regular lattice with arbitrary edge weights; heights are determined by path cost from a set of generator nodes. The shapes of individual terrain features, such as mountains, hills, and craters, are specified by a monotonically decreasing profile describing the cross-sectional shape of a feature, while the locations of features in the terrain are specified by placing the generators. Pathing places ridges whose initial location have a dendritic shape. The method is robust and easy to control, making it possible to create pareidolia effects. It can produce a wide range of realistic synthetic terrains such as mountain ranges, craters, faults, cinder cones, and hills. The algorithm incorporates random graph edge weights, permits the inclusion of multiple topography profiles, and allows precise control over placement of terrain features and their heights. These properties all allow the artist to create highly heterogeneous terrains that compare quite favorably to existing methods.

In the future autonomous vehicles are expected to navigate independently and manage complex traffic situations. This thesis is one of two theses initiated with the aim of researching which methods could be used within the field of autonomous vehicles. The purpose of this thesis was to investigate how Model Predictive Control could be used in the field of autonomous vehicles. The tasks to generate a safe and economic path, to re-plan to avoid collisions with moving obstacles and to operate the vehicle have been studied. The algorithm created is set up as a hierarchical framework defined by a high and a low level planner. The objective of the high level planner is to generate the global route while the objectives of the low level planner are to operate the vehicle and to re-plan to avoid collisions. Optimal Control problems have been formulated in the high level planner for the use of path planning. Different objectives of the planning have been investigated e.g. the minimization of the traveled length between the start and the end point. Approximations of the static obstacles' forbidden areas have been made with circles. A Quadratic Programming framework has been set up in the low level planner to operate the vehicle to follow the high level pre-computed path and to locally re-plan the route to avoid collisions with moving obstacles. Four different strategies of collision avoidance have been implemented and investigated in a simulation environment.

This thesis describes a novel terrain synthesis method based on distances in a weighted graph. The method begins with a regular lattice with arbitrary edge weights; heights are determined by path cost from a set of generator nodes. The shapes of individual terrain features, such as mountains, hills, and craters, are specified by a monotonically decreasing profile describing the cross-sectional shape of a feature, while the locations of features in the terrain are specified by placing the generators. Pathing places ridges whose initial location have a dendritic shape. The method is robust and easy to control, making it possible to create pareidolia effects. It can produce a wide range of realistic synthetic terrains such as mountain ranges, craters, faults, cinder cones, and hills. The algorithm incorporates random graph edge weights, permits the inclusion of multiple topography profiles, and allows precise control over placement of terrain features and their heights. These properties all allow the artist to create highly heterogeneous terrains that compare quite favorably to existing methods.

The main objective of this thesis is to present a new path planning scheme for solving the shortest (collision-free) path problem for an agent (vehicle) operating in a partially known environment. We present two novel algorithms to solve the planning problem. For both of these approaches we assume that the agent has detailed knowledge of the environment and the obstacles only in the vicinity of its current position. Far away obstacles or the final destination are only partially known and may even change dynamically at each instant of time. The path planning scheme is based on information gathered on-line by the available on-board sensor devices. The solution minimizes the total length of the path with respect to a metric that includes actual path length, along with a risk-induced metric. In order to obtain an approximation of the whole configuration space at different levels of fidelity we use a wavelet approximation scheme. In the first proposed algorithm, the path-planning problem is solved using a multi-resolution cell decomposition of the environment obtained from the wavelet transform. In the second algorithm, we extend the results of the the first one by using the multiresolution representation of the environment in conjunction with a conformal mapping to polar coordinates. By performing the cell decomposition in polar coordinates, we can naturally incorporate sector-like cells that are adapted to the data representation collected by the on-board sensor devices.

No description available.

This thesis presents a visual servo control scheme for a ball-and-plate system with a maze. The maze built on the plate forms obstacles for the ball and increases variety and complexity of its environment. The ball-and-plate system is a two degrees-of-freedom robotic wrist with an acrylic plate attached as the end effector. By using image processing techniques, the ball¡¦s position is acquired from the visual feedback, which was implemented with a webcam and a personal computer. A fuzzy controller, which provides dexterity of the robotic wrist, is designed to decide the slope angles of the plate to guide the ball to a designated target spot. Using the method of distance transform, the path planning based on the current position of the ball is conducted to find the shortest path toward the target spot. Besides, a relaxed path, appears to be more suitable for actual applications, is provided by the obstacle¡¦s expansion approach. Experimental results show that the presented control framework successfully leads the ball to pass through the maze and arrive at target spot. The visual servo control scheme works effectively in both stabilization and tracking control. Based on this preliminary achievement, further improvement and deeper exploration on related research topics can be carried on in the future.