In this thesis, questions of navigation, planning and control of real-world mobile robotic systems are addressed. Chapter II contains the first contribution in this thesis, which is a modification of the canonical two-layer hybrid architecture: deliberative planning on top, with reactive behaviors underneath. Deliberative is used to describe higher-level reasoning that includes experiential memory and regional or global objectives. Alternatively, reactive describes low-level controllers that operate on information spatially and temporally immediate to the robot. In the traditional architecture, information is passed top down, with the deliberative layer dictating to the reactive layer. Chapter II presents our work on introducing feedback in the opposite direction, allowing the behaviors to provide information to the planning module(s). The path planning problem, particularly as it as solved by the visibility graph, is addressed first in Chapter III. Our so-called oriented visibility graph is a combinatorial planner with emphasis on dynamic re-planning in unknown environments at the expensive of guaranteed optimality at all times. An example of single source planning -- where the goal location is known and static -- this approach is compared to related approaches (e.g. the reduced visibility graph). The fourth chapter further develops the work presented in the Chapter III; the oriented visibility graph is extended to the hierarchical oriented visibility graph. This work directly addresses some of the limitations of the oriented visibility graph, particularly the loss of optimality in the case where obstacles are non-convex and where the convex hulls of obstacles overlap. This results in an approach that is a kind of middle-ground between the oriented visibility graph which was designed to handle dynamic updates very fast, and the reduced visibility graph, an old standard in path planning that guarantees optimality. Chapter V investigates path planning at a higher level of abstraction. Given is a weighted colored graph where vertices are assigned a color (or class) that indicates a feature or quality of the environment associated with that vertex. The question is then asked, ``what is the globally optimal path through this weighted colored graph?' We answer this question with a mapping from classes and edge weights to a real number, and use Dijkstra's Algorithm to compute the best path. Correctness is proven and an implementation is highlighted.

High-flying unmanned reconnaissance and surveillance systems are now being used extensively in the United States military. Current development programs are producing demonstrations of next-generation unmanned flight systems that are designed to perform combat missions. Their use in first-strike combat operations will dictate operations in densely cluttered environments that include unknown obstacles and threats, and will require the use of terrain for masking. The demand for autonomy of operations in such environments dictates the need for advanced trajectory optimization capabilities. In addition, the ability to coordinate the movements of more than one aircraft in the same area is an emerging challenge. This thesis examines using an analytical reduced order formulation for trajectory generation for minimum time and terrain masking cases. First, pseudo-3D constant velocity equations of motion are used for path planning for a single vehicle. In addition, the inclusion of winds, moving targets and moving threats is considered. Then, this formulation is increased to using 3D equations of motion, both with a constant velocity and with a simplified varying velocity model. Next, the constant velocity equations of motion are expanded to include the simultaneous path planning of an unspecified number of vehicles, for both aircraft avoidance situations and formation flight cases.

In wireless positioning system, in addition to channel error, the geometric re- lationship between sensor nodes and the target may also affect the positioning accuracy. The effect is called geometric dilution of precision (GDOP). GDOP is determined as ratio factor between location error and measurement error. A higher GDOP value indicates a larger location error in location estimation. Accordingly, the location performance will be poor. The GDOP can therefore be used as an in- dex of the positioning performance. In this thesis, approaches of tracking a moving target with extended Kalman filter (EKF) in a time-difference-of-arrival (TDOA) wireless positioning system are discussed. While the target changes its position with time, the geometric layout between sensor nodes and the target will become differ- ent. To maintain the good layout, the positioning system with mobile sensor nodes is considered. Therefore, the geometric layout can be possibly improved and GDOP effect can be reduced by the mobility of mobile sensor nodes. In order to find the positions that mobile sensor nodes should move to, a time-varying function based on the GDOP distribution is defined for finding the best solutions. Since the simu- lated annealing is capable of escaping local minima and finding the global minimum in an objective function, the simulated annealing algorithm is used in finding the best solutions in the defined function. Thus the best solutions can be determined as the destinations of mobile sensor nodes. When relocating mobile sensor nodes from their current positions to the destinations, they may pass through or stay in high GDOP regions before arriving at the destinations. To avoid the problem, we establish an objective function for path planning of mobile sensor nodes in order to minimize the overall positioning accuracy. Simulation results show that the mobile sensor nodes will accordingly change their positions while the target is moving. All the sensor nodes will maintain a surrounding region to localize the target and the GDOP effect can be effectively reduced.

The thesis is to explore wireless location tracking algorithms based on geometric dilution of precision (GDOP) in the mobile environment. The GDOP can be used as an indication of positioning accuracy, affected by the geometric relationship between the target and sensing units. The smaller the GDOP is, the better positioning accuracy. By using the information of sensing units and time difference of arrival (TDOA) positioning method, we use extended Kalman filter as an estimator to track and predict the state of a moving target. From previous research, the lowest GDOP value, located at the center of a regular polygon, represents the best positioning accuracy in 2-D scenario with numerous sensing units. It is important to find the best locations for the sensing units. Simulated annealing algorithm was used in previous studies. However, it only finds a location at a time, and consumes computation load and time. Due to the above-mentioned reasons, we propose a location tracking system, which consists of a base traiver station and numerous mobile sensing units. By using the information of a base transceiver station and the predicted position of target, we can obtain the best locations for all the mobile sensing units with the calculation of rotation matrix. The locations can also be used as beacons for relocating mobile sensing units. It may take many cycles to move mobile sensing units to the best locations. We have to perform path planning for mobile sensing units. Due to the location change of the moving target, the routes need adjustment accordingly. If the predicted stay of a mobile sensing unit is inside the obstacle, we adjust the route of the mobile sensing unit to make it stay out of the obstacle. Therefore, we also propose a path planning scheme for mobile sensing units to avoid obstacles. Through simulations, the proposed method decreases the tracking time effectively, and find the best locations precisely. When mobile sensing units move toward the best locations, they successfully avoid obstacles and move toward the position with the minimum GDOP. Through the course, good positioning accuracy can be maintained.

In recent years, due to the international competition, soaring cost of land and personnel, aging population, low birth rate¡Ketc, resulting in the recession of the competitiveness of traditional industries in Taiwan. Manpower is needed to monitor the manufacturing process, however, only a worker can¡¦t endure such kind of repetitive workload; on the other hand, it¡¦s not economic to hire more workers to share the workload. Therefore, we expect robots to replace human resources in the manufacturing process. With the advance of science and technology, the mobile robot must equip intelligent judgments. For instance, obstacle avoidance, a way to avoid damage being caused by collision with the obstacles. In general, there are some tables, chairs and the electrical equipment in the office. In the dynamic obstacles case, the robot is effective and immediate response to determine while the people are walking, the staff members to maintain a work efficiency, and security through complex environments. It is the primary topics of discussion. Another important function is path planning, such as the patrol, and the global path planning. Let the mobile robot reach the specified target successfully. In the remote monitoring case, let users know the actual situation of the mobile robot. For example, records of patrol information and specify the action type to move. Therefore, this thesis presents a project of the indoor integrated intelligent mobile robots, including obstacle avoidance, path planning, and remote monitoring of the unknown environment.

Unmanned aerial vehicles (UAVs) are becoming increasingly popular for surveillance in civil and military applications. Vehicles built for this purpose vary in their sensing capabilities, speed and maneuverability. It is therefore natural to assume that a team of UAVs given the mission of visiting a set of targets would include vehicles with differing capabilities. This paper addresses the problem of assigning each vehicle a sequence of targets to visit such that the mission is completed with the least "cost" possible given that the team of vehicles is heterogeneous. In order to simplify the problem the capabilities of each vehicle are modeled as cost to travel from one target to another. In other words, if a vehicle is particularly suited to visit a certain target, the cost for that vehicle to visit that target is low compared to the other vehicles in the team. After applying this simplification, the problem can be posed as an instance of the combinatorial problem called the Heterogeneous Travelling Salesman Problem (HTSP). This paper presents a transformation of a Heterogenous, Multiple Depot, Multiple Traveling Salesman Problem (HMDMTSP) into a single, Asymmetric, Traveling Salesman Problem (ATSP). As a result, algorithms available for the single salesman problem can be used to solve the HMDMTSP. To show the effectiveness of the transformation, the well known Lin-Kernighan-Helsgaun heuristic was applied to the transformed ATSP. Computational results show that good quality solutions can be obtained for the HMDMTSP relatively fast. Additional complications to the sequencing problem come in the form of precedence constraints which prescribe a partial order in which nodes must be visited. In this context the sequencing problem was studied seperately using the Linear Program (LP) relaxation of a Mixed Integer Linear Program (MILP) formulation of the combinatorial problem known as the "Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP).

In this thesis, we address the problem of real-time path search in partially observable grid worlds, and propose two single agent and one multi-agent search algorithm. The first algorithm, Real-Time Edge Follow (RTEF), is capable of detecting the closed directions around the agent by analyzing the nearby obstacles, thus avoiding dead-ends in order to reach a static target more effectively. We compared RTEF with a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observed significant improvement. The second algorithm, Real-Time Moving Target Evaluation Search (MTES), is also able to detect the closed directions similar to RTEF, but in addition, determines the estimated best direction that leads to a static or moving target from a shorter path. Employing this new algorithm, we obtain an impressive improvement over RTEF with respect to path length, but at the cost of extra computation. We compared our algorithms with Moving Target Search (MTS) developed by Ishida and the off-line path planning algorithm A*, and observed that MTES performs significanlty better than MTS, and offers solutions very close to optimal ones produced by A*. Finally, we present Multi-Agent Real-Time Pursuit (MAPS) for multiple predators to capture a moving prey cooperatively. MAPS introduces two new coordination strategies namely Blocking Escape Directions (BES) and Using Alternative Proposals (UAL), which help the predators waylay the possible escape directions of the prey in coordination. We compared our coordination strategies with the uncoordinated one, and observed an impressive reduction in the number of moves to catch the prey.

This dissertation is the first attempt to demonstrate the use of magnetic-levitation (maglev) positioners for commercial applications requiring nanopositioning. The key objectives of this research were to devise the control strategies and motion planning to overcome the inherent technical challenges of the maglev systems, and test them on the developed maglev systems to demonstrate their capabilities as the next-generation nanopositioners. Two maglev positioners based on novel actuation schemes and capable of generating all the six-axis motions with a single levitated platen were used in this research. These light-weight single-moving platens have very simple and compact structures, which give them an edge over most of the prevailing nanopositioning technologies and allow them to be used as a cluster tool for a variety of applications. The six-axis motion is generated using minimum number of actuators and sensors. The two positioners operate with a repeatable position resolution of better than 3 nm at the control bandwidth of 110 Hz. In particular, the Y-stage has extended travel range of 5 mm × 5 mm. They can carry a payload of as much as 0.3 kg and retain the regulated position under abruptly and continuously varying load conditions. This research comprised analytical design and development, followed by experimental verification and validation. Preliminary analysis and testing included open-loop stabilization and rigorous set-point change and load-change testing to demonstrate the precision-positioning and load-carrying capabilities of the maglev positioners. Decentralized single-input-single-output (SISO) proportional-integral-derivative (PID) control was designed for this analysis. The effect of actuator nonlinearities were reduced through actuator characterization and nonlinear feedback linearization to allow consistent performance over the large travel range. Closed-loop system identification and order-reduction algorithm were developed in order to analyze and model the plant behavior accurately, and to reduce the effect of unmodeled plant dynamics and inaccuracies in the assembly. Coupling among the axes and subsequent undesired motions and crosstalk of disturbances was reduced by employing multivariable optimal linear-quadratic regulator (LQR). Finally, application-specific nanoscale path planning strategies and multiscale control were devised to meet the specified conflicting time-domain performance specifications. All the developed methodologies and algorithms were implemented, individually as well as collectively, for experimental verification. Some of these applications included nanoscale lithography, patterning, fabrication, manipulation, and scanning. With the developed control strategies and motion planning techniques, the two maglev positioners are ready to be used for the targeted applications.

In wireless location system, geometric relationship between the base station (BS) and the mobile station (MS) may affect the accuracy of MS location estimate. The effect is called Geometric Dilution of Precision (GDOP). Given the information of geometric configuration of BS and MS locations, the GDOP value can be calculated accordingly. In fact, the GDOP value is considered as ratio factor between the location error and measurement noise. A higher GDOP value indicates larger location error in the location estimator. Therefore the GDOP can be utilized as an index for observing the location precision of the MS under different geometric layout. The accuracy of location estimation can be improved by changing the BS device element locations. In the thesis, a time different of arrival (TDOA) wireless location system with mobile base station (MBS) is considered. Changing the geometric layout between the BS and the MS by relocating the MBS, the GDOP effect can be reduced and the accuracy of location estimation also can therefore be improved. Since the simulated annealing (SA) is capable of escaping the local minimum and finding the global minimum in an objective function, the SA algorithm is used in finding the best solution in a defined function based on the GDOP distribution. The best solution is then the destination of an MBS in the process of MS location estimation. When relocating an MBS from its initial location to the best location, it is likely that the MBS enters regions with high GDOP effects. To avoid the problem, the steepest descent (SD) algorithm is utilized for path planning. First, we establish the objective function which consists of the GDOP information and the angle of movement. A nearby location that has the minimum value of objective function is selected as the next move. The process continues until the MBS reaches the destination. A variety of cases are investigated by computer simulations. Simulation results show that the proposed approach can effectively find the best locations for MBSs to relocate. Based on the relocation and path planning, the GDOP effects can be reasonably reduced, and therefore the higher location accuracy is achieved.

<p>The goal of this thesis is to make an unmanned ground vehicle (UGV) follow a given reference trajectory, without colliding with obstacles in its way. This thesis will especially focus on modeling and controlling the UGV, which is based on the power wheelchair Trax from Permobil.</p><p>In order to make the UGV follow a given reference trajectory without colliding, it is crucial to know the position of the UGV at all times. Odometry is used to estimate the position of the UGV relative a starting point. For the odometry to work in a satisfying way, parameters such as wheel radii and wheel base have to be calibrated. Two control signals are used to control the motion of the UGV, one to control the speed and one to control the steering angles of the two front wheels. By modeling the motion of the UGV as a function of the control signals, the motion can be predicted. A path following algorithm is developed in order to make the UGV navigate by maps. The maps are given in advance and do not contain any obstacles. A method to handle obstacles that comes in the way is presented.</p>