Type-omega DPLs

Type-omega DPLs (Denotational Proof Languages) are languages for proof presentation and search that offer strong soundness guarantees. LCF-type systems such as HOL offer similar guarantees, but their soundness relies heavily on static type systems. By contrast, DPLs ensure soundness dynamically, through their evaluation semantics; no type system is necessary. This is possible owing to a novel two-tier syntax that separates deductions from computations, and to the abstraction of assumption bases, which is factored into the semantics of the language and allows for sound evaluation. Every type-omega DPL properly contains a type-alpha DPL, which can be used to present proofs in a lucid and detailed form, exclusively in terms of primitive inference rules. Derived inference rules are expressed as user-defined methods, which are "proof recipes" that take arguments and dynamically perform appropriate deductions. Methods arise naturally via parametric abstraction over type-alpha proofs. In that light, the evaluation of a method call can be viewed as a computation that carries out a type-alpha deduction. The type-alpha proof "unwound" by such a method call is called the "certificate" of the call. Certificates can be checked by exceptionally simple type-alpha interpreters, and thus they are useful whenever we wish to minimize our trusted base. Methods are statically closed over lexical environments, but dynamically scoped over assumption bases. They can take other methods as arguments, they can iterate, and they can branch conditionally. These capabilities, in tandem with the bifurcated syntax of type-omega DPLs and their dynamic assumption-base semantics, allow the user to define methods in a style that is disciplined enough to ensure soundness yet fluid enough to permit succinct and perspicuous expression of arbitrarily sophisticated derived inference rules. We demonstrate every major feature of type-omega DPLs by defining and studying NDL-omega, a higher-order, lexically scoped, call-by-value type-omega DPL for classical zero-order natural deduction---a simple choice that allows us to focus on type-omega syntax and semantics rather than on the subtleties of the underlying logic. We start by illustrating how type-alpha DPLs naturally lead to type-omega DPLs by way of abstraction; present the formal syntax and semantics of NDL-omega; prove several results about it, including soundness; give numerous examples of methods; point out connections to the lambda-phi calculus, a very general framework for type-omega DPLs; introduce a notion of computational and deductive cost; define several instrumented interpreters for computing such costs and for generating certificates; explore the use of type-omega DPLs as general programming languages; show that DPLs do not have to be type-less by formulating a static Hindley-Milner polymorphic type system for NDL-omega; discuss some idiosyncrasies of type-omega DPLs such as the potential divergence of proof checking; and compare type-omega DPLs to other approaches to proof presentation and discovery. Finally, a complete implementation of NDL-omega in SML-NJ is given for users who want to run the examples and experiment with the language.

SOVEREIGN: An Autonomous Neural System for Incrementally Learning Planned Action Sequence to Navigate Towards a Rewarded Goal

How do reactive and planned behaviors interact in real time? How are sequences of such behaviors released at appropriate times during autonomous navigation to realize valued goals? Controllers for both animals and mobile robots, or animats, need reactive mechanisms for exploration, and learned plans to reach goal objects once an environment becomes familiar. The SOVEREIGN (Self-Organizing, Vision, Expectation, Recognition, Emotion, Intelligent, Goaloriented Navigation) animat model embodies these capabilities, and is tested in a 3D virtual reality environment. SOVEREIGN includes several interacting subsystems which model complementary properties of cortical What and Where processing streams and which clarify similarities between mechanisms for navigation and arm movement control. As the animat explores an environment, visual inputs are processed by networks that are sensitive to visual form and motion in the What and Where streams, respectively. Position-invariant and sizeinvariant recognition categories are learned by real-time incremental learning in the What stream. Estimates of target position relative to the animat are computed in the Where stream, and can activate approach movements toward the target. Motion cues from animat locomotion can elicit head-orienting movements to bring a new target into view. Approach and orienting movements are alternately performed during animat navigation. Cumulative estimates of each movement are derived from interacting proprioceptive and visual cues. Movement sequences are stored within a motor working memory. Sequences of visual categories are stored in a sensory working memory. These working memories trigger learning of sensory and motor sequence categories, or plans, which together control planned movements. Predictively effective chunk combinations are selectively enhanced via reinforcement learning when the animat is rewarded. Selected planning chunks effect a gradual transition from variable reactive exploratory movements to efficient goal-oriented planned movement sequences. Volitional signals gate interactions between model subsystems and the release of overt behaviors. The model can control different motor sequences under different motivational states and learns more efficient sequences to rewarded goals as exploration proceeds.

Electromagnetic tracking and steering for catheter navigation

This thesis explores the use of electromagnetics for both steering and tracking of medical instruments in minimally invasive surgeries. The end application is virtual navigation of the lung for biopsy of early stage cancer nodules. Navigation to the peripheral regions of the lung is difficult due to physical dimensions of the bronchi and current methods have low successes rates for accurate diagnosis. Firstly, the potential use of DC magnetic fields for the actuation of catheter devices with permanently magnetised distal attachments is investigated. Catheter models formed from various materials and magnetic tip formations are used to examine the usefulness of relatively low power and compact electromagnets. The force and torque that can be exerted on a small permanent magnet is shown to be extremely limited. Hence, after this initial investigation we turn our attention to electromagnetic tracking, in the development of a novel, low-cost implementation of a GPS-like system for navigating within a patient. A planar magnetic transmitter, formed on a printed circuit board for a low-profile and low cost manufacture, is used to generate a low frequency magnetic field distribution which is detected by a small induction coil sensor. The field transmitter is controlled by a novel closed-loop system that ensures a highly stable magnetic field with reduced interference from one transmitter coil to another. Efficient demodulation schemes are presented which utilise synchronous detection of each magnetic field component experienced by the sensor. The overall tracking accuracy of the system is shown to be less than 2 mm with an orientation error less than 1°. A novel demodulation implementation using a unique undersampling approach allows the use of reduced sample rates to sample the signals of interest without loss of tracking accuracy. This is advantageous for embedded microcontroller implementations of EM tracking systems. The EM tracking system is demonstrated in the pre-clinical environment of a breathing lung phantom. The airways of the phantom are successfully navigated using the system in combination with a 3D computer model rendered from CT data. Registration is achieved using both a landmark rigid registration method and a hybrid fiducial-free approach. The design of a planar magnetic shield structure for blocking the effects of metallic distortion from below the transmitter is presented which successfully blocks the impact of large ferromagnetic objects such as operating tables. A variety of shielding material are analysed with MuMetal and ferrite both providing excellent shieling performance and an increased signal to noise ratio. Finally, the effect of conductive materials and human tissue on magnetic field measurements is presented. Error due to induced eddy currents and capacitive coupling is shown to severely affect EM tracking accuracy at higher frequencies.

Orientation and navigation in bats: known unknowns or unknown unknowns?

Bats have been extensively studied with regard to their ability to orient, navigate and hunt prey by means of echolocation, but almost nothing is known about how they orient and navigate in situations such as migration and homing outside the range of their echolocation system. As volant animals, bats face many of the same problems and challenges as birds. Migrating bats must relocate summer and winter home ranges over distances as far as 2,000 km. Foraging bats must be able to relocate their home roost if they range beyond a familiar area, and indeed circumstantial evidence suggests that these animals can home from more than 600 km. However, an extensive research program on homing and navigation in bats halted in the early 1970s. The field of bird navigation has advanced greatly since that time and many of the mechanisms that birds are known to use for navigation were not known or widely accepted at this time. In this paper I discuss what is known about orientation and navigation in bats and use bird navigation as a model for future research in bat navigation. Technology is advancing such that previous difficulties in studying orientation in bats in the field can be overcome and so that the mechanisms of navigation in this highly mobile animal can finally be elucidated.

Robot and insect navigation by polarized skylight

A study of a large number of published experiments on the behaviour of insects navigating by skylight has led to the design of a system for navigation in lightly clouded skies, suitable for a robot or drone. The design is based on the measurement of the directions in the sky at which the polarization angle, i.e. the angle χ between the polarized E-vector and the meridian, equals ±π/4 or ±(π/4 + π/3) or ±(π/4 - π/3). For any one of these three options, at any given elevation, there are usually 4 such directions and these directions can give the azimuth of the sun accurately in a few short steps, as an insect can do. A simulation shows that this compass is accurate as well as simple and well suited for an insect or robot. A major advantage of this design is that it is close to being invariant to variable cloud cover. Also if at least two of these 12 directions are observed the solar azimuth can still be found by a robot, and possibly by an insect.

Polarized skylight does not calibrate the compass system of a migratory bat

In a recent study, Greif et al. (2014) demonstrated a functional role of polarized light for a bat species confronted with a homing task. These non-migratory bats appeared to calibrate their magnetic compass by using polarized skylight at dusk, yet it is unknown if migratory bats also use these cues for calibration. During autumn migration, we equipped Nathusius' bats, Pipistrellus nathusii, with radio transmitters and tested if experimental animals exposed to a 90° rotated band of polarized light during dusk, would head in a different direction compared with control animals. After release, bats of both groups continued their journey in the same direction. This observation argues against the use of a polarization-calibrated magnetic compass by this migratory bat and questions that the ability of using polarized light for navigation is a consistent feature in bats. This finding matches with observations in some passerine birds that used polarized light for calibration of their magnetic compass before but not during migration.

Autonomous COLREGs Compliant Ship Navigation, Using BridgeSimulators and an Unmanned Vessel

This paper presents an approach to COLREGs compliant ship navigation. A system architecture is proposed, which will be implemented and tested on two platforms: networked bridge simulators and at sea trials using an autonomous unmanned surface vessel. Attention is paid to collision avoidance software and its risk mitigation.

A vision system for detecting paths and moving obstacles for the blind

In this paper we present a monocular vision system for a navigation aid. The system assists blind persons in following paths and sidewalks, and it alerts the user to moving obstacles which may be on collision course. Path borders and the vanishing point are de-tected by edges and an adapted Hough transform. Opti-cal flow is detected by using a hierarchical, multi-scale tree structure with annotated keypoints. The tree struc-ture also allows to segregate moving objects, indicating where on the path the objects are. Moreover, the centre of the object relative to the vanishing point indicates whether an object is approaching or not.

The SmartVision navigation prototype for the blind

The goal of the project "SmartVision: active vision for the blind" is to develop a small and portable but intelligent and reliable system for assisting the blind and visually impaired while navigating autonomously, both outdoor and indoor. In this paper we present an overview of the prototype, design issues, and its different modules which integrate a GIS with GPS, Wi-Fi, RFID tags and computer vision. The prototype addresses global navigation by following known landmarks, local navigation with path tracking and obstacle avoidance, and object recognition. The system does not replace the white cane, but extends it beyond its reach. The user-friendly interface consists of a 4-button hand-held box, a vibration actuator in the handle of the cane, and speech synthesis. A future version may also employ active RFID tags for marking navigation landmarks, and speech recognition may complement speech synthesis.

Biologically Inspired Vision for Indoor Robot Navigation

Ultrasonic, infrared, laser and other sensors are being applied in robotics. Although combinations of these have allowed robots to navigate, they are only suited for specific scenarios, depending on their limitations. Recent advances in computer vision are turning cameras into useful low-cost sensors that can operate in most types of environments. Cameras enable robots to detect obstacles, recognize objects, obtain visual odometry, detect and recognize people and gestures, among other possibilities. In this paper we present a completely biologically inspired vision system for robot navigation. It comprises stereo vision for obstacle detection, and object recognition for landmark-based navigation. We employ a novel keypoint descriptor which codes responses of cortical complex cells. We also present a biologically inspired saliency component, based on disparity and colour.

The smart vision local navigation aid for blind and visually impaired persons

The SmartVision prototype is a small, cheap and easily wearable navigation aid for blind and visually impaired persons. Its functionality addresses global navigation for guiding the user to some destiny, and local navigation for negotiating paths, sidewalks and corridors, with avoidance of static as well as moving obstacles. Local navigation applies to both in- and outdoor situations. In this article we focus on local navigation: the detection of path borders and obstacles in front of the user and just beyond the reach of the white cane, such that the user can be assisted in centering on the path and alerted to looming hazards. Using a stereo camera worn at chest height, a portable computer in a shoulder-strapped pouch or pocket and only one earphone or small speaker, the system is inconspicuous, it is no hindrence while walking with the cane, and it does not block normal surround sounds. The vision algorithms are optimised such that the system can work at a few frames per second.

An internet DGPS service for precise outdoor navigation

The goal of the work presented in this paper is to provide mobile platforms within our campus with a GPS based data service capable of supporting precise outdoor navigation. This can be achieved by providing campus-wide access to real time Differential GPS (DGPS) data. As a result, we designed and implemented a three-tier distributed system that provides Internet data links between remote DGPS sources and the campus and a campus-wide DGPS data dissemination service. The Internet data link service is a two-tier client/server where the server-side is connected to the DGPS station and the client-side is located at the campus. The campus-wide DGPS data provider disseminates the DGPS data received at the campus via the campus Intranet and via a wireless data link. The wireless broadcast is intended for portable receivers equipped with a DGPS wireless interface and the Intranet link is provided for receivers with a DGPS serial interface. The application is expected to provide adequate support for accurate outdoor campus navigation tasks.

Fly by data link: feasibility of a relative navigation solution for aviation relying on a future L-band data link

Trabalho final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações

Un oeil sur la langue : aspects neuro-cognitifs du processus de la navigation chez l'aveugle-né

La vision est un élément très important pour la navigation en général. Grâce à des mécanismes compensatoires les aveugles de naissance ne sont pas handicapés dans leurs compétences spatio-cognitives, ni dans la formation de nouvelles cartes spatiales. Malgré l’essor des études sur la plasticité du cerveau et la navigation chez les aveugles, les substrats neuronaux compensatoires pour la préservation de cette fonction demeurent incompris. Nous avons démontré récemment (article 1) en utilisant une technique d’analyse volumétrique (Voxel-Based Morphometry) que les aveugles de naissance (AN) montrent une diminution de la partie postérieure de l’hippocampe droit, structure cérébrale importante dans la formation de cartes spatiales. Comment les AN forment-ils des cartes cognitives de leur environnement avec un hippocampe postérieur droit qui est significativement réduit ? Pour répondre à cette question nous avons choisi d’exploiter un appareil de substitution sensorielle qui pourrait potentiellement servir à la navigation chez les AN. Cet appareil d’affichage lingual (Tongue display unit -TDU-) retransmet l’information graphique issue d’une caméra sur la langue. Avant de demander à nos sujets de naviguer à l’aide du TDU, il était nécessaire de nous assurer qu’ils pouvaient « voir » des objets dans l’environnement grâce au TDU. Nous avons donc tout d’abord évalué l’acuité « visuo »-tactile (article 2) des sujets AN pour les comparer aux performances des voyants ayant les yeux bandées et munis du TDU. Ensuite les sujets ont appris à négocier un chemin à travers un parcours parsemé d’obstacles i (article 3). Leur tâche consistait à pointer vers (détection), et contourner (négociation) un passage autour des obstacles. Nous avons démontré que les sujets aveugles de naissance non seulement arrivaient à accomplir cette tâche, mais encore avaient une performance meilleure que celle des voyants aux yeux bandés, et ce, malgré l’atrophie structurelle de l’hippocampe postérieur droit, et un système visuel atrophié (Ptito et al., 2008). Pour déterminer quels sont les corrélats neuronaux de la navigation, nous avons créé des routes virtuelles envoyées sur la langue par le biais du TDU que les sujets devaient reconnaitre alors qu’ils étaient dans un scanneur IRMf (article 4). Nous démontrons grâce à ces techniques que les aveugles utilisent un autre réseau cortical impliqué dans la mémoire topographique que les voyants quand ils suivent des routes virtuelles sur la langue. Nous avons mis l’emphase sur des réseaux neuronaux connectant les cortex pariétaux et frontaux au lobe occipital puisque ces réseaux sont renforcés chez les aveugles de naissance. Ces résultats démontrent aussi que la langue peut être utilisée comme une porte d’entrée vers le cerveau en y acheminant des informations sur l’environnement visuel du sujet, lui permettant ainsi d’élaborer des stratégies d’évitement d’obstacles et de se mouvoir adéquatement.

Study of baleen whales’ ecology and interaction with maritime traffic activities to support management of a complex socio-ecological system

Thesis written in co-mentorship with Robert Michaud.