This work describes path finding among obstacles in 3D space using probabilistic algorithms. Users can create scene in application GUI - define start object, obstacles, goal position and run probabilistic algorithm. The finding path is visualized. The work describes probabilistic algorithm, collision detection and the basics of 3D graphics and shows design and implementation of an application created.

Exploration is of interest for autonomous mapping and rescue applications using unmanned vehicles. The objective is to, without any prior information, explore all initially unmapped space. We present a system that can perform fast and efficient exploration of large scale arbitrary 3D environments. We combine frontier exploration planning (FEP) as a global planning strategy, together with receding horizon planning (RH-NBVP) for local planning. This leads to plans that incorporate information gain along the way, but do not get stuck in already explored regions. Furthermore, we make the potential information gain estimation more efficient, through sparse ray-tracing, and caching of already estimated gains. The worked carried out in this thesis has been published as a paper in Robotand Automation letters and presented at the International Conference on Robotics and Automation in Montreal 2019.

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.

No description available.

La conception de protéines ayant des propriétés spécifiques représente un enjeu majeur pour la pharmacologie et les bio-technologies. Malgré les progrès des méthodes de CAO développées pour la conception de protéines, une limitation majeure des techniques existantes vient de la difficulté à prendre en compte la mobilité du squelette protéique, afin de mieux capturer l’ensemble des propriétés des protéines candidates et garantir la bonne stabilité de la protéine choisie dans la conformation voulue. De plus, si des méthodes de conception multi-états ont été proposées, elles ne permettent pas de garantir l’existence d’une trajectoire réaliste entre ces états. De ce fait, la conception de protéines devant permettre la transition entre plusieurs états reste un problème hors de la portée des méthodes actuelles. Cette thèse explore comment des algorithmes inspirés de la robotique peuvent être utilisés pour explorer l’espace conformationnel de manière efficace afin d’améliorer les méthodes de conception de protéines en prenant en compte de manière plus poussée la flexibilité de leur squelette. Ce travail pose également un premier jalon vers une méthode de conception adaptée à la réalisation d’un mouvement de la protéine. / The ability to design proteins with specific properties would yield great progress in pharmacology and bio-technologies. Methods to design proteins have been developed since a few decades and some relevant achievements have been made including de novo protein design. Yet, current approaches suffer some serious limitations. By not taking protein’s backbone motions into account, they fail at capturing some of the properties of the candidate design and cannot guarantee that the solution will in fact be stable for the goal conformation. Besides, although multi-states design methods have been proposed, they do not guarantee that a feasible trajectory between those states exists, which means that design problem involving state transitions are out of reach of the current methods. This thesis investigates how robotics-inspired algorithms can be used to efficiently explore the conformational landscape of a protein aiming to enhance protein design methods by introducing additional backbone flexibility. This work also provides first milestones towards protein motion design.

The present work examines waypoint selection and evaluation mechanisms for data muling water sensor nodes via unmanned air vehicle. We present a mathematical model for predicting signal strength with respect to distance and height using a two-ray propagation model in conjunction with the individual radiation patterns of transmitting and receiving antennas. Signal quality over space is then be used to select best waypoints. Packet reception rate is related to the received signal strength indicator through experimentation and serves as a data efficiency indicator. Both models are then used to gather performance metrics of several simple path planning schemes. Both hover-only and in-flight communication are compared. Packet reception rate limitations were found to dramatically limit the effectiveness of waypoint selection regardless of power efficiency.

When tracking a moving target, an Unmanned Aerial Vehicle (UAV) mustkeep the target within its sensory range while simultaneously remaining awareof its surroundings. However, small flight computers must have sufficientenvironmental knowledge and computational capabilities to provide real-timecontrol to function without a ground station connection. Using a Raspberry Pi4 model B, this thesis presents a practical implementation for evaluating pathplanning generators in the context of following a moving target. The practicalmodel integrates two waypoint generators for the path planning scenario: A*and 3D Vector Field Histogram* (3DVFH*). The performances of the pathplanning algorithms are evaluated in terms of the required processing time,distance from the target, and memory consumption. The simulations are runin two types of environments. One is modelled by hand with a target walkinga scripted path. The other is procedurally generated with a random walker.The study shows that 3DVFH* produces paths that follow the moving targetmore closely when the actor follows the scripted path. With a random walker,A* consistently achieves the shortest distance. Furthermore, the practicalimplementation shows that the A* algorithm’s persistent approach to detectand track objects has a prohibitive memory requirement that the Raspberry Pi4 with a 2GBRAMcannot handle. Looking at the impact of object density, the3DVFH* implementation shows no impact on distance to the moving target,but exhibits lower execution speeds at an altitude with fewer obstacles to detect.The A* implementation has a marked impact on execution speeds in the formof longer distances to the target at altitudes with dense obstacle detection.This research project also realized a communication link between thepath planning implementations and a Geographical Information System (GIS)application supported by the Carmenta Engine SDK to explore how locallystored geospatial information impact path planning scenarios. Using VMapgeospatial data, two levels of increasing geographical resolution werecompared to show no performance impact on the planner processes, but asignificant addition in memory consumption. Using geospatial informationabout a region of interest, the waypoint generation implementations are ableto query the map application about the legality of its current position. / När en obemannade luftfarkost, även kallad drönare, spårar ett rörligt mål, måste drönaren behålla målet inom sensorisk räckvidd medan den håller sig uppdaterad om sin omgivning. Små flygdatorer måste dock ha tillräckligt med information om sin omgivning och nog med beräkningsresurser för att erbjuda realtidskontroll utan kommunikation med en markstation. Genom att använda en Raspberry Pi 4 modell B presenterar denna studie en praktisk applicering utav vägplanerare som utvärderas utifrån deras lämplighet att följa ett rörligt mål. Den praktiska implementationen jämför två vägplaneringsalgoritmer: A* och 3D Vector Field Histogram* (3DVFH*). Vägplaneringsalgoritmernas prestanda utvärderas genom att studera deras hastighet, avstånd från målet och minnesresurser. Vägplaneringsalgoritmerna utvärderas i två situationer. Den första är en simulationsvärld som är gjord för hand där målet rör sig efter en fördefinierad väg. Den andra är en procedurellt genererad värld där målet rör sig slumpmässigt. Studien visar att 3DVFH* producerar vägar som håller drönaren närmare målet när målet rör sig efter en fördefinierad väg. Med en slumpvandring i en procedurell värld är A* närmast målet. Resultaten från Raspberry Pi visar också att A* algoritmen sätter prohibitivt höga minneskrav på Raspberry Pi 4 som bara har 2GBRAM. Studerar man påverkan av synbara objekt på avståndet till målet så ser man ingen för 3DVFH* algoritmens egenskap att hålla sig nära, men man ser snabbare bearbetningshastighet när det är färre objekt att upptäcka. A* algoritmen ser en påverkan på dess distans från målet när fler objekt finns att upptäcka. Denna studie visar också hur en kommunikationslänk mellan vägplaneringsalgoritmer och kartapplikationer som stöds utav Carmenta Engine SDK skall implementeras. Detta används för att studera hur lokal geografisk information kan användas i ett spårningssammanhang. Genom att använda två nivåer av geografisk upplösning från VMap data, jämförs påverkan på vägplaneringarnas prestanda. Studien visar att ingen påverkan på prestandan kan ses men att kartapplikationen kräver mer minnesresurser. Genom att använda geografisk information om en region av intresse visar denna applikation hur vägplaneringsalgoritmerna kan fråga kartapplikationen om legaliteten om sin nuvarande position.

No description available.

Developing regions are often characterized by large areas that are poorly reachable or explored. The mapping and census of roaming populations in these areas are often difficult and sporadic. A recent spark in the development of small aerial vehicles has made them the perfect tool to efficiently and accurately monitor these areas. This paper presents an approach to aid area surveying through the use of Unmanned Aerial Vehicles. The two main components of this approach are an efficient on-device deep learning object identification component to capture and infer images with acceptable performance (latency andaccuracy), and a dynamic path planning approach, informed by the object identification component. In particular, this thesis illustrates the development of the path planning component, which exploits potential field methods to dynamically adapt the path based on inputs from the vision system. It also describes the integration work that was performed to implement the approach on a prototype platform, with the aim to achieve autonomous flight with onboard computation. The path planning component was developed with the purpose of gaining information about the populations detected by the object identification component, while considering the limited resources of energy and computational power onboard a UAV. The developed algorithm was compared to navigation using a predefined path, where the UAV does not react to the environment. Results from the comparison show that the algorithm provide more information about the objects of interest, with a very small change in flight time. The integration of the object identification and the path planning components on the prototype platform was evaluated in terms of end-to-end latency, power consumption and resource utilization. Results show that the proposed approach is feasible for area surveying in developing regions. Parts of this work has been published in the workshop of DroNet, collocated with MobiSys, with the title Surveying Areas in Developing Regions Through Context Aware Drone Mobility. Thework was carried out in collaboration with Alessandro Montanari, Alice Valentini, Cecilia Mascoloand Amanda Prorok. / Utvecklingsländer är ofta karaktäriserade av vidsträcka områden som är svåråtkomliga och outforskade. Kartläggning och folkräkning av populationen i dessa områden är svåra uppgifter som sker sporadiskt. Nya framsteg i utvecklingen av små, luftburna fordon har gjort dem till perfekta verktyg för att effektivt och noggrant bevaka dessa områden. Den här rapporten presenterar en strategi för att underlätta utforskning av dessa områden med hjälp av drönare. De två huvudkomponenterna i denna strategi är en effektiv maskininlärningskomponent för objektidentifiering med acceptabel prestanda i avseende av latens och noggrannhet, samt en dynamisk navigeringskomponent som informeras av objektidentifieringskomponenten. I synnerhet illustrerar denna avhandling utvecklingen av navigeringskomponenten, som utnyttjar potentialfält för att dynamiskt anpassa vägen baserat på information från objektidentifieringssystemet. Dessutom beskrivs det integrationsarbete som utförts för att implementera strategin på en prototypplattform, med målet att uppnå autonom flygning med all beräkning utförd ombord. Navigeringskomponenten utvecklades i syfte att maximera informationen om de populationer som upptäckts av objektidentifieringskomponenten, med hänsyn till de begränsade resurserna av energi och beräkningskraft ombord på en drönare. Den utvecklade algoritmen jämfördes med navigering med en fördefinierad väg, där drönaren inte reagerar på omgivningen. Resultat från jämförelsen visar att algoritmen ger mer information om objekten av intresse, med en mycket liten förändring i flygtiden. Integreringen av objektidentifieringskomponenten och navigeringskomponenten på prototypplattformen utvärderades med avseende på latens, strömförbrukning och resursutnyttjande. Resultaten visar att den föreslagna strategin är genomförbar för kartläggning och utforskning av utvecklingsregioner. Delar av detta arbete har publicerats i DroNets workshop, samlokaliserad med MobiSys, med titeln Surveying Areas in Developing Regions Through Context Aware Drone Mobility. Arbetet utfördes i samarbete med Alessandro Montanari, Alice Valentini, Cecilia Mascolo och Amanda Prorok.

Simulation is an important tool for prediction and assessment of the behavior of complex systems and situations. The importance of simulation has increased tremendously during the last few decades, mainly because the rapid pace of development in the field of electronics has turned the computer from a costly and obscure piece of equipment to a cheap ubiquitous tool which is now an integral part of our daily lives. While such technological improvements make it easier to analyze well-understood deterministic systems, increase in speed and storage capacity alone are not enough when simulating situations where human beings and their behavior are an integral part of the system being studied. The problem with simulation of intelligent entities is that intelligence is still not well understood and it seems that the field of Artificial Intelligence (AI) has a long way to go before we get computers to think like humans. Behavior-based agent modeling has been proposed in mid-80's as one of the alternatives to the classical AI approach. While used mainly for the control of specialized robotic vehicles with very specific sensory capabilities and limited intelligence, we believe that a behavior-based approach to modeling generic autonomous agents in complex environments can provide promising results. To this end, we are investigating a behavior-based model for controlling groups of collaborating and competing agents in a geographic terrain. In this thesis, we are focusing on scenarios of military nature, where agents can move within the environment and adversaries can eliminate each other through use of weapons. Different aspects of agent behavior like navigation to a goal or staying in group formation, are implemented by distinct behavior modules and the final observed behavior for each agent is an emergent property of the combination of simple behaviors and their interaction with the environment. Our experiments show that while such an approach is quite efficient in terms of computational power, it has some major drawbacks. One of the problems is that reactive behavior-based navigation algorithms are not well suited for environments with complex mobility constraints where they tend to perform much worse than proper path planning. This problem represents an important research question, especially when it is considered that most of the modern military conflicts and operations occur in urban environments. One of the contributions of this thesis is a novel approach to reactive navigation where goals and terrain information are fused based on the idea of transforming a terrain with obstacles into a virtual obstacle-free terrain. Experimental results show that our approach can successfully combine the low run-time computational complexity of reactive methods with the high success rates of classical path planning. Another interesting research problem is how to deal with the unpredictable nature of emergent behavior. It is not uncommon to have situations where an outcome diverges significantly from the intended behavior of the agents due to highly complex nonlinear interactions with other agents or the environment itself. Chances of devising a formal way to predict and avoid such abnormalities are slim at best, mostly because such complex systems tend to be be chaotic in nature. Instead, we focus on detection of deviations through tracking group behavior which is a key component of the total situation awareness capability required by modern technology-oriented and network-centric warfare. We have designed a simple and efficient clustering algorithm for tracking of groups of agent suitable for both spatial and behavioral domain. We also show how to detect certain events of interest based on a temporal analysis of the evolution of discovered clusters.