As automated cockpit systems become increasingly complex, they often become more difficult for the pilot to interact with. Such complex systems often essentially dictate methods of safe operation. Sometimes dynamic changes in situation demand re-planning the aircrafts route of flight and the pilot must use automation to accomplish this task. However, this replanning in-flight can be a difficult task. From a pilots point of view, any flight can be thought of as a plan of turns and descents, as well as changes in aircraft dynamics. Planning can be broadly classified into three categories based on a timeline for planning, namely, strategic planning, tactical planning and time-critical planning. Tactical planning, the focus of this thesis, usually occurs in an order of minutes. Although immediate safety is an important concern, other measures of efficiency (e.g. time to land, fuel burn, passenger comfort) may also be factored in by the pilot when he/she has the time to do so. The objective of this research, therefore, was to gain insight into strategies and behavior of pilots during tactical planning and the impact of automation on planning performance and behavior. The experiment studied how pilots planned their flight when given a non-nominal or an emergency situation (when the flight planning is to be performed by the pilot) and how automation can aided them in their planning. In addition to studying the planning behavior of pilots and the impact of automation on this process, this research also provided insight for development of flight deck replanning tools and a preliminary investigation of an intelligent cockpit aid capable of autonomously generating a flight plan. The complexity of such a system limits the scope of this research to examining only a simulated pre-scripted prototype of the system.

Um agente de planejamento em Inteligência Artificial deve estar preparado para lidar com aspectos dinâmicos do domínio, ou seja, com os efeitos de suas ações, bem como com mudanças provocadas por outros agentes (eventos exógenos). Neste caso, é possível identificar duas situações distintas: todas as informações necessárias sobre a dinâmica do ambiente são, de alguma forma, modeladas pelo agente e consideradas durante o planejamento; ou o agente não possui conhecimento completo do ambiente, sendo que as ações exógenas só são percebidas durante a execução do plano. Neste último caso, podem ocorrer falhas na execução das ações do agente, por exemplo, as pré-condições nas quais o plano se baseia deixam de ser verdadeiras e a meta do agente pode não ser mais alcançável. Para garantir que o agente saia da situação de plano inválido e alcance seu conjunto de metas originais, é preciso fazer um \"reparo de plano\" ou \"replanejamento\". Enquanto no replanejamento o agente abandona o plano original e constrói um novo plano para o estado atual, o reparo de plano tenta fazer um compromisso com o plano original, gerando o menor número de mudanças possível para que o novo plano atinja as metas do problema original. O processo de reparo de plano envolve duas operações básicas: (a) remover do plano as ações que estejam impedindo a execução do mesmo e (b) adicionar novas ações a fim de atingir as metas. A proposta deste trabalho é aplicar e implementar o método de reparo de plano chamado de \"refinamento reverso\". O sistema de reparo implementado será capaz de realizar duas operações: adicionar ações por meio dos procedimentos clássicos de refinamento de planos e remover ações por refinamento reverso com a adição de heurísticas para melhorar o desempenho da tarefa de reparo. / An Artificial Intelligence planning agent must be prepared to deal with dynamic aspects of the domain, in other words, with its actions effects as well as the changes caused by other agents (exogenous events). In this case it is possible to identify two situations: all the necessary information about the environment dynamics are modeled by the agent and considered during the planning; or the agent has an incomplete knowledge about the environment and the exogenous events are only noted during the plan execution. In the latter case, some actions can fail, e.g. because some preconditions are no longer satisfied implying that the goals may not be achieved anymore. To make sure that the agent leaves the invalid plan situation and reach its original goals, it is necessary to make a \"plan repair\" or \"replanning\". While in the replanning the agent discards the original plan and makes a new one for the present condition, the plan repair tries to make a commitment with the original plan, making the least changes necessary to achieve the goals of the original problem. The plan repair process involves two basic operations: (a) remove the actions that are blocking the plan to be executed and (b) add new actions to achieve the goals. The proposal of this work is to apply and implement the repair method called \"unrefinement\". This repair system will be able to perform two operations: add actions through plan refinement classical procedures, and remove actions by this new method called unrefinement with addition of heuristics to improve the repair task performance.

When attempting to follow ground-based moving objects (hereafter referred to as ``waldos'') using an unmanned air vehicle (UAV), occlusion can become a significant problem for computer vision algorithms designed to track the object. When a waldo is occluded, the computer vision algorithm loses the track and the UAV's ability to predict movement degrades. We propose a path-planning and replanning method that moves a UAV to a location that maximizes the important waldos that can be seen while accounting for occlusion, and attempts to maximize the area it can see during travel. The proposed work moves beyond state-of-the-art algorithms designed to follow a single waldo while accounting for occlusion to enable tracking multiple prioritized waldos.

Um agente de planejamento em Inteligência Artificial deve estar preparado para lidar com aspectos dinâmicos do domínio, ou seja, com os efeitos de suas ações, bem como com mudanças provocadas por outros agentes (eventos exógenos). Neste caso, é possível identificar duas situações distintas: todas as informações necessárias sobre a dinâmica do ambiente são, de alguma forma, modeladas pelo agente e consideradas durante o planejamento; ou o agente não possui conhecimento completo do ambiente, sendo que as ações exógenas só são percebidas durante a execução do plano. Neste último caso, podem ocorrer falhas na execução das ações do agente, por exemplo, as pré-condições nas quais o plano se baseia deixam de ser verdadeiras e a meta do agente pode não ser mais alcançável. Para garantir que o agente saia da situação de plano inválido e alcance seu conjunto de metas originais, é preciso fazer um \"reparo de plano\" ou \"replanejamento\". Enquanto no replanejamento o agente abandona o plano original e constrói um novo plano para o estado atual, o reparo de plano tenta fazer um compromisso com o plano original, gerando o menor número de mudanças possível para que o novo plano atinja as metas do problema original. O processo de reparo de plano envolve duas operações básicas: (a) remover do plano as ações que estejam impedindo a execução do mesmo e (b) adicionar novas ações a fim de atingir as metas. A proposta deste trabalho é aplicar e implementar o método de reparo de plano chamado de \"refinamento reverso\". O sistema de reparo implementado será capaz de realizar duas operações: adicionar ações por meio dos procedimentos clássicos de refinamento de planos e remover ações por refinamento reverso com a adição de heurísticas para melhorar o desempenho da tarefa de reparo. / An Artificial Intelligence planning agent must be prepared to deal with dynamic aspects of the domain, in other words, with its actions effects as well as the changes caused by other agents (exogenous events). In this case it is possible to identify two situations: all the necessary information about the environment dynamics are modeled by the agent and considered during the planning; or the agent has an incomplete knowledge about the environment and the exogenous events are only noted during the plan execution. In the latter case, some actions can fail, e.g. because some preconditions are no longer satisfied implying that the goals may not be achieved anymore. To make sure that the agent leaves the invalid plan situation and reach its original goals, it is necessary to make a \"plan repair\" or \"replanning\". While in the replanning the agent discards the original plan and makes a new one for the present condition, the plan repair tries to make a commitment with the original plan, making the least changes necessary to achieve the goals of the original problem. The plan repair process involves two basic operations: (a) remove the actions that are blocking the plan to be executed and (b) add new actions to achieve the goals. The proposal of this work is to apply and implement the repair method called \"unrefinement\". This repair system will be able to perform two operations: add actions through plan refinement classical procedures, and remove actions by this new method called unrefinement with addition of heuristics to improve the repair task performance.

Web services have become a prominent paradigm for building of both inter and intra-enterprise business processes. These processes are composed from existing Web services based on defined requirements. Standards and techniques have been developed to aid in the dynamic composition of services. However, these approaches are limited when it comes to the handling of unexpected events. This dissertation presents the results of experiments that investigated numerous problems related to Web service composition processes. Based on the investigation, a fault taxonomy was formulated. Faults were grouped into three broad categories, each representing a distinct problem stage. The investigation into faults gave rise to the issue of fault recovery and continued process execution. A list of requirements for self-healing Web service composition was identified, while a new self-healing cycle was exploited based on the MAPE cycle (Monitor, Analyzer, Planner, Executive). The proposed self-healing composition cycle consists of three modules: Plan Generation Module, Plan Execution Module and Failure Analysis Module. The plan execution module, consisting of the execution and run-time monitoring phases, and the failure analysis module, consisting of the analysis and sensemaking phases, were found to be vital to self-healing Web service composition. Self healing Web service composition and the goal of self-healing were achieved through the use of Hierarchical Task Network (HTN) planning systems. / Dissertation (MSc)--University of Pretoria, 2009. / Computer Science / unrestricted

This dissertation models human intent for a robot navigation task, managed by a human and undertaken by a robot in a dynamic, multi-objective environment. Intent is expressed by a human through a user interface and then translated into a robot trajectory that satisfies a set of human-specified objectives and constraints. For a goal-based robot navigation task in a dynamic environment, intent includes expectations about a path in terms of objectives and constraints to be met. If the planned path drifts from the human's intent as the environment changes, a new path needs to be planned. The intent framework has four elements: (a) a mathematical representation of human intent within a multi-objective optimization problem; (b) design of an interactive graphical user interface that enables a human to communicate intent to the robot and then to subsequently monitor intent execution; (c) integration and adoption of a fast online path-planning algorithms that generate solutions/trajectories conforming to the given intent; and (d) design of metric-based triggers that provide a human the opportunity to correct or adapt a planned path to keep it aligned with intent as the environment changes. Key contributions of the dissertation are: (i) design and evaluation of different user interfaces to express intent, (ii) use of two different metrics, cosine similarity and intent threshold margin, that help quantify intent, and (iii) application of the metrics in path (re)planning to detect intent mismatches for a robot navigating in a dynamic environment. A set of user studies including both controlled laboratory experiments and Amazon Mechanical Turk studies were conducted to evaluate each of these dissertation components.

A aplicação de técnicas baseadas em amostragem em algoritmos que envolvem o planejamento de trajetórias de robôs tem se tornado cada vez mais difundida. Deste grupo, um dos algoritmos mais utilizados é chamado Rapidly-exploring Random Tree (RRT), que se baseia na amostragem incremental para calcular de forma eficiente os planos de trajetória do robô evitando colisões com obstáculos. Vários esforços tem sido realizados a fim de reduzir o custo computacional do algoritmo RRT, visando aplicações que necessitem de respostas mais rápidas do algoritmo, como, por exemplo, em ambientes dinâmicos. Um dos dilemas relacionados ao RRT está na etapa de geração de primitivas de movimento. Se várias primitivas são geradas, permitindo o robô executar vários movimentos básicos diferentes, um grande custo computacional é gasto. Por outro lado, quando poucas primitivas são geradas e, consequentemente, poucos movimentos básicos são permitidos, o robô pode não ser capaz de encontrar uma solução para o problema, mesmo que esta exista. Motivados por este problema, um método de geração de primitivas de movimento foi proposto. Tal método é comparado com os métodos tradicional e aleatório de geração de primitivas, considerando não apenas o custo computacional de cada um, mas também a qualidade da solução obtida. O método proposto é aplicado ao algoritmo RRT, que depois é aplicado em um caso de estudo em um ambiente dinâmico. No estudo de caso, o algoritmo RRT otimizado é avaliado em termos de seus custos computacionais durante planejamentos e replanejamento de trajetória. As simulações são realizadas em dois simuladores: um desenvolvido em linguagem Python e outro em Matlab. / The application of sample-based techniques in path-planning algorithms has become year-by-year more widespread. In this group, one of the most widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot\'s path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm.

A aplicação de técnicas baseadas em amostragem em algoritmos que envolvem o planejamento de trajetórias de robôs tem se tornado cada vez mais difundida. Deste grupo, um dos algoritmos mais utilizados é chamado Rapidly-exploring Random Tree (RRT), que se baseia na amostragem incremental para calcular de forma eficiente os planos de trajetória do robô evitando colisões com obstáculos. Vários esforços tem sido realizados a fim de reduzir o custo computacional do algoritmo RRT, visando aplicações que necessitem de respostas mais rápidas do algoritmo, como, por exemplo, em ambientes dinâmicos. Um dos dilemas relacionados ao RRT está na etapa de geração de primitivas de movimento. Se várias primitivas são geradas, permitindo o robô executar vários movimentos básicos diferentes, um grande custo computacional é gasto. Por outro lado, quando poucas primitivas são geradas e, consequentemente, poucos movimentos básicos são permitidos, o robô pode não ser capaz de encontrar uma solução para o problema, mesmo que esta exista. Motivados por este problema, um método de geração de primitivas de movimento foi proposto. Tal método é comparado com os métodos tradicional e aleatório de geração de primitivas, considerando não apenas o custo computacional de cada um, mas também a qualidade da solução obtida. O método proposto é aplicado ao algoritmo RRT, que depois é aplicado em um caso de estudo em um ambiente dinâmico. No estudo de caso, o algoritmo RRT otimizado é avaliado em termos de seus custos computacionais durante planejamentos e replanejamento de trajetória. As simulações são realizadas em dois simuladores: um desenvolvido em linguagem Python e outro em Matlab. / The application of sample-based techniques in path-planning algorithms has become year-by-year more widespread. In this group, one of the most widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot\'s path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm.

O presente documento tem por objetivo apresentar a tese desenvolvida no programa de doutorado em Ciência da Computação e Matemática Computacional do ICMC/USP. Esta tese aborda o desenvolvimento de sistemas autônomos, de baixo custo, para supervisão de missão e segurança de voo em Veículos Aéreos Não Tripulados (VANTs). A supervisão da missão é assegurada através da implementação de um sistema do tipo Mission Oriented Sensor Array (MOSA), responsável pelo adequado cumprimento da missão. A segurança de voo é garantida pelo sistema In-Flight Awareness (IFA), que visa monitorar o funcionamento da aeronave. Os assuntos missão e segurança são complexos e os sistemas MOSA e IFA foram idealizados e desenvolvidos de forma independente, fundamentando-se na ideia de separação de interesses. O desenvolvimento desses sistemas foi baseado em dois modelos de referência: MOSA e IFA, propostos pela literatura. Em trabalhos anteriores da literatura, alguns sistemas do tipo MOSA e IFA foram propostos para situações específicas de missão. Numa outra abordagem, esta tese propõe um único sistema MOSA e IFA capaz de se adequar a um conjunto distinto de missões. Neste trabalho, foi desenvolvida toda arquitetura de comunicação que integra os sistemas MOSA e IFA. No entanto, apenas esses dois sistemas não são suficientes para fazer a execução da missão com segurança, necessitando-se de um sistema capaz de se comunicar com o Piloto Automático (AP) do VANT. Logo, um sistema capaz de enviar requisições e comandos ao AP foi também implementado. Através desses três sistemas, missões autônomas com desvio de obstáculos puderam ser realizadas sem intervenção humana, mesmo diante de situações críticas ao voo. Assegurar os aspectos de segurança e missão pode se tornar conflitante durante o voo, pois em situações emergenciais deve-se abortar a missão. Diferentes estratégias para planejamento e replanejamento de rotas, baseadas em computação evolutiva e heurísticas, foram desenvolvidas e integradas nos sistemas MOSA e IFA. Os sistemas, aqui propostos, foram validados em quatro etapas: (i) experimentos com o simulador de voo FlightGear; (ii) simulações com a técnica Software-In-The-Loop (SITL); (iii) simulações com a técnica Hardware-In- The-Loop (HITL); (iv) voos reais. Na última etapa, os sistemas foram embarcados em dois modelos de VANTs, desenvolvidos pelo grupo de pesquisa. Durante a experimentação, alguns modelos de pilotos automáticos (APM e Pixhawk), computadores de bordo (Raspberry Pi 3, Intel Edison e BeagleBone Black), planejadores de missão e replanejadores de rotas emergenciais foram avaliados. Ao todo, três planejadores de rotas e oito replanejadores são suportados pela plataforma autônoma. O sistema autônomo desenvolvido permite alterar missões com diferentes características de hardware e de software de forma fácil e transparente, sendo, desse modo, uma arquitetura com características plug and play. / This document aims to present the thesis developed in the doctoral program in Computer Science and Computational Mathematics at ICMC/USP. This thesis addresses the development of low- cost autonomous systems for mission supervision and flight safety in Unmanned Aerial Vehicles (UAVs). The mission supervision is ensured through the implementation of a Mission Oriented Sensor Array (MOSA) system, which is responsible for the proper fulfillment of the mission. The flight safety is guaranteed by the In-Flight Awareness (IFA) system, which aims to monitor the aircraft operation. The mission and safety issues are complex, and the MOSA and IFA systems were idealized and developed independently, based on the idea of separation of concerns. The development of these systems was based on two reference models: MOSA and IFA, proposed in the literature. In previous works of the literature, some MOSA and IFA systems have been proposed for specific mission situations. In another approach, this thesis proposes a single MOSA and IFA system capable of adapting to a distinct set of missions. All the communication architecture that integrates the MOSA and IFA systems were developed in this work. However, only these two systems are not sufficient to carry out the mission safely; a system that can communicate with the AutoPilot (AP) of the UAV its also needed. In this way, a system that is capable of sending commands and requests to the AP was implemented in this work. Through these three systems, autonomous missions with a diversion of obstacles could be carried out without human intervention, even in critical situations to the flight. Ensuring the safety and mission aspects can become conflicting during the flight because in hazards situations the mission must be aborted. Different strategies for path planning and path replanning, based on evolutionary computation and heuristics, were developed and integrated into the MOSA and IFA systems. The systems proposed here were validated in four stages: (i) experiments with FlightGear flight simulator; (ii) simulations using Software-In-The-Loop (SITL); (iii) simulations using Hardware- In-The-Loop (HITL); (iv) real flights. In the last stage, the systems were embedded in two models of UAVs, developed by the research group. During the experiment were evaluated some models of autopilots (APM and Pixhawk), companion computers (Raspberry Pi 3, Intel Edison and BeagleBone Black), mission planners and emergency route planners. In all, three route planners and eight replanners are supported by the autonomous platform. The developed autonomous system allows changing missions with different hardware and software characteristics in an easy and transparent way, being, therefore, an architecture with Plug and play characteristics.

Ces dernières années, les engins robotisés n’ont cessé d’améliorer leur autonomie dans le domaine de la décision. Désormais, pour ne citer que l’exemple de véhicules aériens, nombre de drones sont largement capables, sans intervention d’un opérateur humain, de décoller, suivre un itinéraire en activant divers capteurs à des moments précis, atterrir en un lieu spécifié, suivre une cible, patrouiller sur une zone... Une des étapes suivantes consiste à faire collaborer une équipe de véhicules autonomes, de nature hétérogène (aériens, terrestres, marins...) afin de leur permettre d’accomplir des missions plus complexes. L’aspect dynamique de l’environnement réel, la non disponibilité à tout instant des moyens de communication, la coordination nécessaire des véhicules,de conceptions parfois différentes, dans l’exécution de certaines parties d’un plan de mission, sont autant d’obstacles à surmonter. Ce travail tente non seulement d’apporter quelques éléments de réponse face à ces difficultés, mais consiste aussi en la mise en place concrète d’un superviseur haut niveau, capable de gérer l’exécution d’une mission par une équipe de véhicules autonomes hétérogènes, où le rôle de l’opérateur humain est volontairement réduit. Nous décrivons dans ce mémoire l’architecture distribuée que nous avons choisi de mettre en œuvre pour répondre à ce problème. Il s’agit d’un superviseur, réparti à bord des véhicules autonomes, interfacé avec leur architecture locale et en charge de l’exécution de la mission d’équipe. Nous nous intéressons également à la formalisation des connaissances nécessaires au déroulement de cette mission, afin d’améliorer l’interopérabilité des véhicules de l’équipe, mais aussi pour expliciter les relations entre modèles décisionnels abstraits et réalité d’exécution concrète. Le superviseur est capable de réagir face aux aléas qui vont se produire dans un environnement dynamique. Nous présentons ainsi dans un second temps les stratégies mises en place pour parvenir à les détecter au mieux, ainsi que la façon dont nous procédons pour réparer partiellement ou totalement le plan de mission initial, afin de remplir les objectifs initiaux. Nous nous basons notamment sur la nature hiérarchique du plan de mission, mais aussi sur celle de la structure de sous-équipes que nous proposons de construire. Enfin, nous présentons quelques résultats obtenus expérimentalement, sur des missions simulées et des scénarios réels, notamment ceux du Programme d’Etudes Amont Action dans lequel s’inscrivent ces travaux de thèse. / Many autonomous robots with specific control oriented architectures have already been developed worldwide.The advance of the work in this field has led researchers wonder for many years to what extent robots would be able to be integrated into a team consisting of autonomous and heterogeneous vehicles with complementary functionalities. However, robot cooperation in a real dynamic environment under unreliable communication conditions remains challenging, especially if these autonomous vehicles have different individual control architectures.In order to address this problem, we have designed a decision software architecture, distributed on each vehicle.This decision layer aims at managing execution and at increasing the fault tolerance of the global system. The mission plan is assumed to be hierarchically structured. ln case of failure detection, the plan repair is done as locally as possible, based on the hierarchical organization.This allows us to restrict message exchange only between the vehicles concerned by the repair process. Knowledge formalisation is also a part of the study permitting the improvement of interoperability between team members. It also provides relevant information all along mission execution, from initial planning computation to plan repair in this multirobot context. The feasibility of the system has been evaluated by simulations and real experiments thanks to the Action project (http://action.onera.fr/welcome/).