Thesis (M. Eng.)--Carleton University, 1992. / Also available in electronic format on the Internet.

In this thesis, we propose algorithms designed for monitoring hazardous agents. Because hazardous environmental monitoring is either tedious or dangerous for human operators, we seek a fully automated robotic system that can help humans. However, there are still many challenges from hardware design to algorithm design that restrict robots to be applied to practical applications. Among these challenges, we are particularly interested in dealing with algorithmic challenges primarily caused by sensing and communication limitations of robots. We develop algorithms with provable guarantees that map and track hazards using a team of robots. Our contributions are as follows. First, we address a situation where the number of hazardous agents is unknown and varies over time. We propose a search and tracking framework that can extract individual target tracks as well as estimate the number and the spatial density of targets. Second, we consider a team of robots tracking individual targets under limited bandwidth. We develop distributed algorithms that can find solutions in bounded amount of time. Third, we propose an algorithm for aerial robots that explores a translating hazardous plume of unknown size and shape. We present a recursive depth-first search-based algorithm that yields a constant competitive ratio for exploring a translating plume. Last, we take into account a heterogeneous team of robots to map and sample a translating plume. These contributions can be applied to a team of aerial robots and a robotic boat monitoring and sampling a translating hazardous plume over a lake. In this application, the aerial robots coordinate with each other to explore the plume and to inform the robotic boat while the robotic boat collects water samples for offline analysis. We demonstrate the performance of our algorithms through simulations and proof-of-concept field experiments for real-world environmental monitoring. / Doctor of Philosophy / Quick response to hazards is crucial as the hazards may put humans at risk and thorough removal of hazards may take a substantial amount of time. Our vision is that the introduction of a robotic solution would be beneficial for hazardous environmental monitoring. Not only the fact that humans can be released from dangerous or tedious tasks, but we also can take advantage of the robot's agile maneuverability and its precise sensing. However, the development on both hardware and software is not yet ripe to be able to deploy autonomous robots in real-world scenarios. Moreover, partial and uncertain information of hazards impose further challenges. In this these, we present various research problems addressing these challenges in hazardous environmental monitoring. Particularly, we are interested in overcoming challenges from the perspective of software by designing planning and decision-making algorithms for robots. We validate our proposed algorithms through extensive simulations and real-world experiments.

In this research, a set of novel, integrated and systematic adaptive process planning algorithms and strategies, which include adaptive tool-path generation algorithms and strategies, adaptive slicing algorithms and strategies, adaptive approach for FGM(Functionally Graded Material)-based biomedical model and build time and geometrical accuracy analysis and control modules, for complex biomedical model fabrication in the RP/M (Rapid Prototyping and Manufacturing) process, have been developed to balance and optimise the geometrical accuracy and build efficiency. In the developed adaptive tool-path generation algorithms and strategies, directly slicing algorithm and NURBS(Non-Uniform Rational B-Spline)-based curves have been developed to represent the boundary contours of the sliced layers to maintain the geometrical accuracy of original biomedical models. The developed mixed tool-path generation algorithm can be used to generate mixed contour and zigzag tool-paths to preserve geometrical accuracy and speed up fabrication. Based on the developed build time and geometrical accuracy analysis modules, the developed adaptive speed algorithms can be used to further reduce build time of biomedical model fabrication in RP/M. In the developed adaptive slicing approach, rotating slicing and two thresholds have been introduced to extract surface feature of biomedical models. Then, an adaptive slicing thickness determination algorithm has been developed to decide the thickness of each slicing layer based on the outside surface complexity of the model. In addition, the user can balance the geometrical accuracy and the build efficiency during RP/M processing with the different values of two pre-setting thresholds. Furthermore, by choosing the right value of the pre-setting thresholds, it can also effectively reduce the build time and improve the accuracy of biomedical model fabrication in RP/M. In the developed adaptive approach for FGM-based biomedical model fabrication, FGM-based modelling features can represents typical FGM-based biomedical models effectively, and the linear and non-linear control parameters for FGM composition and distributions can enable users to address their specific functional needs of FGM-based biomedical model. The proposed mixed tool-path generation algorithm and adaptive speed algorithm can be used to generate a series of contour/offset tool-paths to represent the material gradual change, and zigzag tool-path is generated for the internal area of a single material to support the realizable and customized FGM-based biomedical models fabrication in RP/M efficiently.

<p dir="ltr">Introduces a new framework and state-of-the-art algorithm in closed-loop prediction for motion planning under differential constraints. More specifically, this work introduces the idea of sampling on specific "sampling regions" rather than the entire workspace to speed-up the motion planning process by orders of magnitude.</p>

Thesis (MScEng)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: This project concerns motion planning for a rotary wing UAV, where vehicle controllers are already in place, and map data is readily available to a collision detection module. In broad terms, the goal of the motion planning algorithm is to provide a safe (i.e. obstacle free) flight path between an initial- and goal waypoint. This project looks at two specific motion planning algorithms, the Rapidly Exploring Random Tree (or RRT*), and the Probabilistic Roadmap Method (or PRM). The primary focus of this project is learning how these algorithms behave in specific environments and an in depth analysis is done on their differences. A secondary focus is the execution of planned paths via a Simulink simulation and lastly, this project also looks at the effect of path replanning. The work done in this project enables a rotary wing UAV to autonomously navigate an uncertain, dynamic and cluttered environment. The work also provides insight into the choice of an algorithm for a given environment: knowing which algorithm performs better can save valuable processing time and will make the entire system more responsive. / AFRIKAANSE OPSOMMING: ’n Tipiese vliegstuuroutomaat is daartoe in staat om ’n onbemande lugvaartvoertuig (UAV) so te stuur dat ’n stel gedefinieerde punte gevolg word. Die punte moet egter vooraf beplan word, en indien enige verandering nodig is (bv. as gevolg van veranderinge in die omgewing) is dit nodig dat ’n menslike operateur betrokke moet raak. Vir voertuie om ten volle outonoom te kan navigeer, moet die voertuig in staat wees om te kan reageer op veranderende situasies. Vir hierdie doel word kinodinamiese beplanningsalgoritmes en konflikdeteksiemetodes gebruik. Hierdie projek behels kinodinamiese beplanningsalgoritmes vir ’n onbemande helikopter, waar die beheerders vir die voertuig reeds in plek is, en omgewingsdata beskikbaar is vir ’n konflikdeteksie-module. In breë terme is die doel van die kinodinamiese beplanningsalgoritme om ’n veilige (d.w.s ’n konflikvrye) vlugpad tussen ’n begin- en eindpunt te vind. Hierdie projek kyk na twee spesifieke kinodinamiese beplanningsalgoritmes, die “Rapidly exploring Random Tree*” (of RRT*), en die “Probabilistic Roadmap Method” (of PRM). Die primêre fokus van hierdie projek is om die gedrag van hierdie algoritmes in spesifieke omgewings te analiseer en ’n volledige analise te doen op hul verskille. ’n Sekondêre fokus is die uitvoering van ’n beplande vlugpad d.m.v ’n Simulink-simulasie, en laastens kyk hierdie projek ook na die effek van padherbeplanning. Die werk wat gedoen is in hierdie projek stel ’n onbemande helikopter in staat om outonoom te navigeer in ’n onsekere, dinamiese en besige omgewing. Die werk bied ook insig in die keuse van ’n algoritme vir ’n gegewe omgewing: om te weet watter algoritme beter uitvoertye het kan waardevolle verwerkingstyd bespaar, en verseker dat die hele stelsel vinniger kan reageer.

Web services provide a standardized means of publishing diverse, distributed applications. Increasingly, corporations are providing services or programs within and between organizations either on corporate intranets or on the cloud. Many of these services can be composed together, ideally automatically, to provide value-added service. Automated Web service composition is an example of such automation where given a specification of an objective to be realized and some knowledge of the state of the world, the problem is to automatically select, integrate, and invoke multiple services to achieve the specified objective. A popular approach to the Web service composition problem is to conceive it as an Artificial Intelligence planning task. This enables us to bring to bear many of the theoretical and computational advances in reasoning about actions to the task of Web service composition. However, Web service composition goes far beyond the reaches of classical planning, presenting a number of interesting challenges relevant to a large body of problems related to the composition of actions, programs, and services. Among these, an important challenge is generating not only a composition, but a high-quality composition tailored to user preferences. In this thesis, we present an approach to the Web service composition problem with a particular focus on the customization of compositions. We claim that there is a correspondence between generating a customized composition of Web services and non-classical Artificial Intelligence planning where the objective of the planning problem is specified as a form of control knowledge, such as a workflow or template, together with a set of constraints to be optimized or enforced. We further claim that techniques in (preference-based) planning can provide a computational basis for the development of effective, state-of-the-art techniques for generating customized compositions of Web services. To evaluate our claim, we characterize the Web service composition problem with customization as a non-classical planning problem, exploit and advance preference specification languages and preference-based planning, develop algorithms tailored to the Web service composition problem, prove formal properties of these algorithms, implement proof-of-concept systems, and evaluate these systems experimentally. While our research has been motivated by Web services, the theory and techniques we have developed are amenable to analogous problems in such diverse sectors as multi-agent systems, business process modeling, component software composition, and social and computational behaviour modeling and verification.

Web services provide a standardized means of publishing diverse, distributed applications. Increasingly, corporations are providing services or programs within and between organizations either on corporate intranets or on the cloud. Many of these services can be composed together, ideally automatically, to provide value-added service. Automated Web service composition is an example of such automation where given a specification of an objective to be realized and some knowledge of the state of the world, the problem is to automatically select, integrate, and invoke multiple services to achieve the specified objective. A popular approach to the Web service composition problem is to conceive it as an Artificial Intelligence planning task. This enables us to bring to bear many of the theoretical and computational advances in reasoning about actions to the task of Web service composition. However, Web service composition goes far beyond the reaches of classical planning, presenting a number of interesting challenges relevant to a large body of problems related to the composition of actions, programs, and services. Among these, an important challenge is generating not only a composition, but a high-quality composition tailored to user preferences. In this thesis, we present an approach to the Web service composition problem with a particular focus on the customization of compositions. We claim that there is a correspondence between generating a customized composition of Web services and non-classical Artificial Intelligence planning where the objective of the planning problem is specified as a form of control knowledge, such as a workflow or template, together with a set of constraints to be optimized or enforced. We further claim that techniques in (preference-based) planning can provide a computational basis for the development of effective, state-of-the-art techniques for generating customized compositions of Web services. To evaluate our claim, we characterize the Web service composition problem with customization as a non-classical planning problem, exploit and advance preference specification languages and preference-based planning, develop algorithms tailored to the Web service composition problem, prove formal properties of these algorithms, implement proof-of-concept systems, and evaluate these systems experimentally. While our research has been motivated by Web services, the theory and techniques we have developed are amenable to analogous problems in such diverse sectors as multi-agent systems, business process modeling, component software composition, and social and computational behaviour modeling and verification.

Os Veículos Aéreos Não Tripulados (VANTs) são ideais para operações de risco e estressante para o ser humano são as chamadas dull, dirty and dangerous missions. Portanto, uma importante aplicação desse tipo de robô aéreo diz respeito a operações de busca envolvendo múltiplos VANTs cooperativos, em que há risco de colisões entre aeronaves e o tempo de um voo é limitado, entre outros fatores, pela capacidade de um piloto trabalhar sem descanso. Entretanto, apesar de atualmente verificar-se um crescente número de pesquisas envolvendo VANTs e do grande potencial existente na utilização de VANTs, operações de busca cooperativas ainda não estão ocorrendo. Esse assunto é uma área de estudo multidisciplinar e nascente, que possui diversas linhas de pesquisa. Diferentes algoritmos de navegação e padrões de busca foram estudados visando selecionar o(s) mais adequado(s). Além disso, apresenta-se, neste trabalho, uma visão geral sobre os mecanismos de coordenação multiagente e avalia a adequação de cada uma delas à coordenação distribuída de agentes (VANTs), visando cooperação. Assim, com o objetivo de melhorar o desempenho de uma operação de busca, esta pesquisa de mestrado propõe um modelo de VANTs cooperativos que combina mecanismos de coordenação multiagente, algoritmos de navegação e padrões de busca estabelecidos pelos principais órgãos responsáveis pelas operações de busca e salvamento. Visando avaliar a sensibilidade do percentual médio de detecção de objetos, bem como o tempo médio de busca, foi desenvolvido um simulador e milhares de simulações foram realizadas. Observou-se que, utilizando o modelo, VANTs cooperativos podem reduzir, em média, 57% do tempo de busca (comparando com uma busca de dois VANTs não cooperativos no mesmo cenário), mantendo a probabilidade média de detecção dos objetos próxima de 100% e sobrevoando apenas 30% do espaço de busca. / There are an increasing number of researches into UAV (Unmanned Aerial Vehicle) in the literature. These robots are quite suitable to dull, dirty and dangerous missions. Thus, an important application of these vehicles is the search operations involving multiple UAVs in which there is risk of collisions among aircrafts and the flight time is limited by the maximum time of pilot working hours. However, despite the huge potential use of the UAVs, cooperative search operations with this kind of flying robots are not yet occurring. This research topic is a new and multidisciplinary area of study in its beginning and there are several issues that can be studied, such as centralized versus decentralized control, path planning for cooperative flights, agent reasoning for UAV tactical planning, safety assessments, reliability in automatic target reconnaissance by cameras, agent coordination mechanisms applied to UAV cooperation and the application itself. Different path planning algorithms were studied aiming to attain the most suitable to these kinds of operations, and the conclusions are presented. In addition, official documents of Search and Rescue operations are also studied in order to know the best practices already established for this kind of operations, and, finally, an overview of the coordination multi-agent theory is presented and evaluated to achieve the UAV coordination. This work proposes a model that combines path planning algorithms, search patterns and multi-agent coordination techniques to obtain a cooperative UAV model. The great goal for cooperative UAV is to achieve such performance that the performance of the group overcomes the sum of the individual performances isolatedly. Then, aiming to analyze the average percentage of objects detection, and the average search time, a simulator was developed and thousands of simulations were run. It was observed that, using the proposed model, two cooperative UAVs can perform a search operation 57% faster than two non cooperative UAVs, keeping the average probability of objects detection approaching at 100% and flying only 30% of the search space.

Os Veículos Aéreos Não Tripulados (VANTs) são ideais para operações de risco e estressante para o ser humano são as chamadas dull, dirty and dangerous missions. Portanto, uma importante aplicação desse tipo de robô aéreo diz respeito a operações de busca envolvendo múltiplos VANTs cooperativos, em que há risco de colisões entre aeronaves e o tempo de um voo é limitado, entre outros fatores, pela capacidade de um piloto trabalhar sem descanso. Entretanto, apesar de atualmente verificar-se um crescente número de pesquisas envolvendo VANTs e do grande potencial existente na utilização de VANTs, operações de busca cooperativas ainda não estão ocorrendo. Esse assunto é uma área de estudo multidisciplinar e nascente, que possui diversas linhas de pesquisa. Diferentes algoritmos de navegação e padrões de busca foram estudados visando selecionar o(s) mais adequado(s). Além disso, apresenta-se, neste trabalho, uma visão geral sobre os mecanismos de coordenação multiagente e avalia a adequação de cada uma delas à coordenação distribuída de agentes (VANTs), visando cooperação. Assim, com o objetivo de melhorar o desempenho de uma operação de busca, esta pesquisa de mestrado propõe um modelo de VANTs cooperativos que combina mecanismos de coordenação multiagente, algoritmos de navegação e padrões de busca estabelecidos pelos principais órgãos responsáveis pelas operações de busca e salvamento. Visando avaliar a sensibilidade do percentual médio de detecção de objetos, bem como o tempo médio de busca, foi desenvolvido um simulador e milhares de simulações foram realizadas. Observou-se que, utilizando o modelo, VANTs cooperativos podem reduzir, em média, 57% do tempo de busca (comparando com uma busca de dois VANTs não cooperativos no mesmo cenário), mantendo a probabilidade média de detecção dos objetos próxima de 100% e sobrevoando apenas 30% do espaço de busca. / There are an increasing number of researches into UAV (Unmanned Aerial Vehicle) in the literature. These robots are quite suitable to dull, dirty and dangerous missions. Thus, an important application of these vehicles is the search operations involving multiple UAVs in which there is risk of collisions among aircrafts and the flight time is limited by the maximum time of pilot working hours. However, despite the huge potential use of the UAVs, cooperative search operations with this kind of flying robots are not yet occurring. This research topic is a new and multidisciplinary area of study in its beginning and there are several issues that can be studied, such as centralized versus decentralized control, path planning for cooperative flights, agent reasoning for UAV tactical planning, safety assessments, reliability in automatic target reconnaissance by cameras, agent coordination mechanisms applied to UAV cooperation and the application itself. Different path planning algorithms were studied aiming to attain the most suitable to these kinds of operations, and the conclusions are presented. In addition, official documents of Search and Rescue operations are also studied in order to know the best practices already established for this kind of operations, and, finally, an overview of the coordination multi-agent theory is presented and evaluated to achieve the UAV coordination. This work proposes a model that combines path planning algorithms, search patterns and multi-agent coordination techniques to obtain a cooperative UAV model. The great goal for cooperative UAV is to achieve such performance that the performance of the group overcomes the sum of the individual performances isolatedly. Then, aiming to analyze the average percentage of objects detection, and the average search time, a simulator was developed and thousands of simulations were run. It was observed that, using the proposed model, two cooperative UAVs can perform a search operation 57% faster than two non cooperative UAVs, keeping the average probability of objects detection approaching at 100% and flying only 30% of the search space.

Les récents développements des systèmes technologiques ont mené à une complexification des comportements des systèmes actuels. Une solution pour gérer cette complexité croissante consiste à les considérer comme un ensemble de sous-systèmes hétérogènes et à développer des techniques distribuées pour les contrôler et les gérer. Cette solution soulève plusieurs problèmes. Tout d’abord, l’augmentation de la taille et du nombre de composants entraîne immanquablement l’augmentation du nombre de fautes qui peuvent conduire le système dans un état de défaillance critique. De fait, parmi les fonctions opérationnelles, les tâches de détection et d’isolation des fautes (Fault Detection and Isolation ou FDI), de maintenance et de réparation sont devenues prédominantes et elles influent considérablement sur le coût total des produits finaux.Cette thèse porte sur la détection et l’isolation de fautes. Parmi les différentes méthodes pour générer des tests de diagnostic utilisant la redondance analytique, cette thèse adopte l’approche par espace de parité qui utilise les relations de redondance analytique (RRA). Étant donné un modèle du système sous la forme d’un ensemble d’équations différentielles, les RRA sont des relations obtenues à partir du modèle en éliminant les variables non mesurées. Ceci peut être effectué dans un cadre analytique en utilisant la théorie de l’élimination. Une autre solution consiste à utiliser l’analyse structurelle. L’analyse structurelle est basée sur une abstraction du modèle qui ne conserve que les liens entre variables et équations. Malgré son apparente simplicité, l’analyse structurelle fournit un ensemble d’outils puissants, s’appuyant sur la théorie des graphes, pour analyser et inférer des informations sur le système. Par ailleurs, elle a l’avantage de s’appliquer indifféremment sur les systèmes linéaires ou non linéaires.L’objectif de cette thèse est de développer des techniques efficaces basées sur l’analyse structurelle pour le diagnostic des systèmes continus distribué. Dans ce cadre, le système se décompose en un ensemble de sous-systèmes en fonction de contraintes fonctionnelles, géographiques ou de confidentialité. La thèse se divise principalement en deux parties :• la première partie cherche à mettre à lumière, à partir des modèles structurels obtenus au niveau des sous-systèmes, les redondances qui généreront des tests de diagnostic pertinents au niveau du système global,• la deuxième partie vise à formuler et résoudre le problème d’optimisation lié au choix d’un sous-ensemble de tests de diagnostic au niveau des sous-systèmes permettant une diagnosticabilité maximale pour le système global.La première partie utilise le concept d’ensemble minimal structurellement surdéterminé guidé par les fautes (Fault-Driven Minimal Structurally Overdetermined Set ou FMSO set). Ce concept est introduit dans la thèse. Il s’agit d’un sousensemble d’équations du modèle avec une redondance minimale à partir de laquelle une RRA sensible à un ensemble de fautes peut être obtenu. Deux solutions pour générer des ensembles FMSO pour le système global sont présentées, d’une part dans un cadre décentralisé avec des superviseurs imbriqués suivant une hiérarchie; d’autre part dans un cadre totalement distribué. Ces solutions sont basées sur les propriétés des ensembles FMSO au niveau des sous-systèmes qui sont présentées dans la thèse. La deuxième partie pose un problème d’optimisation dans le cadre d’une recherche heuristique et propose trois solutions basées sur un algorithme A* itératif combiné avec une fonction capable d’évaluer si un ensemble FMSO au niveau global peut être obtenu à partir des ensembles FMSO locaux sélectionnés. Les concepts introduits dans la thèse et les résultats sont appliqués à deux cas d’étude industriels. Le premier est une usine de désalinisation. Le second est un système de détermination et de contrôle d’attitude pour un satellite en orbite basse. / The recent development of technological systems implies a high complexity of behaviors for today’s systems. An answer to the increased system’s complexity is to look at them as a multitude of heterogeneous subsystems and develop distributed techniques to control and manage them. This raises a number of problems. Firstly, as the size and number of components increase, so does the number of fault occurrences that may drive the system to undergo critical failures. Fault detection and isolation (FDI), maintenance and repair are an increasing part of the operational everyday’s tasks and they impact drastically the total cost of final products.This thesis focuses on fault detection and isolation. Among the different methods to generate diagnosis tests by taking advantage of analytical redundancy, this thesis adopts the so-called parity space approach based on analytical redundancy relations (ARRs). Given a model of the system in the form of a set of differential equations, ARRs are relations that are obtained from the model by eliminating non measured variables. This can be performed in an analytical framework using elimination theory but another way of doing this is to use structural analysis. Structural analysis is based on a structural abstraction of the model that only retains a representation of which variables are involved in which equations. Despite the rusticity of the abstract model, structural analysis provides a set of powerful tools, relying on graph theory, to analyze and infer information about the system. Interestingly, it applies indifferently to linear or nonlinear systems. The goal of this thesis is to develop effective techniques based on structural analysis for diagnosis of distributed continuous systems. In this framework, the system is decomposed into a set of subsystems according to functional, geographical or privacy constraints. The thesis is organized in two parts:• highlighting the redundancies that are built into the global structural model and that can be used to generate diagnosis tests starting from the redundancies existing in the subsystem’s models,• formulating and solving the optimization problem linked to the choice of a subset of diagnosis tests at the subsystems level that can lead to a set of diagnosis tests achieving maximum diagnosability for the global system.The first part takes benefit of the concept of Fault-Driven Minimal Structurally Overdetermined Set (FMSO set) that is introduced in the thesis. An FMSO set determines a subset of equations of the model with minimal redundancy from which an ARR sensitive to a set of faults can be obtained. Two solutions for generating FMSOs for the global system are presented, in a decentralized framework with supervisors at each level of a hierarchy and in a totally distributed framework.These are based on the properties of the FMSO sets for the subsystems in relation to those of the global system derived in the thesis.