-
A Hybrid Deep Learning Classification of Perimetric Glaucoma Using Peripapillary Nerve Fiber Layer Reflectance and Other OCT Parameters from Three Anatomy Regions
Authors:
Ou Tan,
David S. Greenfield,
Brian A. Francis,
Rohit Varma,
Joel S. Schuman,
David Huang,
Dongseok Choi
Abstract:
Precis: A hybrid deep-learning model combines NFL reflectance and other OCT parameters to improve glaucoma diagnosis. Objective: To investigate if a deep learning model could be used to combine nerve fiber layer (NFL) reflectance and other OCT parameters for glaucoma diagnosis. Patients and Methods: This is a prospective observational study where of 106 normal subjects and 164 perimetric glaucoma…
▽ More
Precis: A hybrid deep-learning model combines NFL reflectance and other OCT parameters to improve glaucoma diagnosis. Objective: To investigate if a deep learning model could be used to combine nerve fiber layer (NFL) reflectance and other OCT parameters for glaucoma diagnosis. Patients and Methods: This is a prospective observational study where of 106 normal subjects and 164 perimetric glaucoma (PG) patients. Peripapillary NFL reflectance map, NFL thickness map, optic head analysis of disc, and macular ganglion cell complex thickness were obtained using spectral domain OCT. A hybrid deep learning model combined a fully connected network (FCN) and a convolution neural network (CNN) to develop and combine those OCT maps and parameters to distinguish normal and PG eyes. Two deep learning models were compared based on whether the NFL reflectance map was used as part of the input or not. Results: The hybrid deep learning model with reflectance achieved 0.909 sensitivity at 99% specificity and 0.926 at 95%. The overall accuracy was 0.948 with 0.893 sensitivity and 1.000 specificity, and the AROC was 0.979, which is significantly better than the logistic regression models (p < 0.001). The second best model is the hybrid deep learning model w/o reflectance, which also had significantly higher AROC than logistic regression models (p < 0.001). Logistic regression with reflectance model had slightly higher AROC or sensitivity than the other logistic regression model without reflectance (p = 0.024). Conclusions: Hybrid deep learning model significantly improved the diagnostic accuracy, without or without NFL reflectance. Hybrid deep learning model, combining reflectance/NFL thickness/GCC thickness/ONH parameter, may be a practical model for glaucoma screen purposes.
△ Less
Submitted 5 June, 2024;
originally announced June 2024.
-
VADER: Visual Affordance Detection and Error Recovery for Multi Robot Human Collaboration
Authors:
Michael Ahn,
Montserrat Gonzalez Arenas,
Matthew Bennice,
Noah Brown,
Christine Chan,
Byron David,
Anthony Francis,
Gavin Gonzalez,
Rainer Hessmer,
Tomas Jackson,
Nikhil J Joshi,
Daniel Lam,
Tsang-Wei Edward Lee,
Alex Luong,
Sharath Maddineni,
Harsh Patel,
Jodilyn Peralta,
Jornell Quiambao,
Diego Reyes,
Rosario M Jauregui Ruano,
Dorsa Sadigh,
Pannag Sanketi,
Leila Takayama,
Pavel Vodenski,
Fei Xia
Abstract:
Robots today can exploit the rich world knowledge of large language models to chain simple behavioral skills into long-horizon tasks. However, robots often get interrupted during long-horizon tasks due to primitive skill failures and dynamic environments. We propose VADER, a plan, execute, detect framework with seeking help as a new skill that enables robots to recover and complete long-horizon ta…
▽ More
Robots today can exploit the rich world knowledge of large language models to chain simple behavioral skills into long-horizon tasks. However, robots often get interrupted during long-horizon tasks due to primitive skill failures and dynamic environments. We propose VADER, a plan, execute, detect framework with seeking help as a new skill that enables robots to recover and complete long-horizon tasks with the help of humans or other robots. VADER leverages visual question answering (VQA) modules to detect visual affordances and recognize execution errors. It then generates prompts for a language model planner (LMP) which decides when to seek help from another robot or human to recover from errors in long-horizon task execution. We show the effectiveness of VADER with two long-horizon robotic tasks. Our pilot study showed that VADER is capable of performing complex long-horizon tasks by asking for help from another robot to clear a table. Our user study showed that VADER is capable of performing complex long-horizon tasks by asking for help from a human to clear a path. We gathered feedback from people (N=19) about the performance of the VADER performance vs. a robot that did not ask for help. https://google-vader.github.io/
△ Less
Submitted 30 May, 2024; v1 submitted 24 May, 2024;
originally announced May 2024.
-
Identifying Fairness Issues in Automatically Generated Testing Content
Authors:
Kevin Stowe,
Benny Longwill,
Alyssa Francis,
Tatsuya Aoyama,
Debanjan Ghosh,
Swapna Somasundaran
Abstract:
Natural language generation tools are powerful and effective for generating content. However, language models are known to display bias and fairness issues, making them impractical to deploy for many use cases. We here focus on how fairness issues impact automatically generated test content, which can have stringent requirements to ensure the test measures only what it was intended to measure. Spe…
▽ More
Natural language generation tools are powerful and effective for generating content. However, language models are known to display bias and fairness issues, making them impractical to deploy for many use cases. We here focus on how fairness issues impact automatically generated test content, which can have stringent requirements to ensure the test measures only what it was intended to measure. Specifically, we review test content generated for a large-scale standardized English proficiency test with the goal of identifying content that only pertains to a certain subset of the test population as well as content that has the potential to be upsetting or distracting to some test takers. Issues like these could inadvertently impact a test taker's score and thus should be avoided. This kind of content does not reflect the more commonly-acknowledged biases, making it challenging even for modern models that contain safeguards. We build a dataset of 601 generated texts annotated for fairness and explore a variety of methods for classification: fine-tuning, topic-based classification, and prompting, including few-shot and self-correcting prompts. We find that combining prompt self-correction and few-shot learning performs best, yielding an F1 score of 0.79 on our held-out test set, while much smaller BERT- and topic-based models have competitive performance on out-of-domain data.
△ Less
Submitted 1 May, 2024; v1 submitted 23 April, 2024;
originally announced April 2024.
-
Major TOM: Expandable Datasets for Earth Observation
Authors:
Alistair Francis,
Mikolaj Czerkawski
Abstract:
Deep learning models are increasingly data-hungry, requiring significant resources to collect and compile the datasets needed to train them, with Earth Observation (EO) models being no exception. However, the landscape of datasets in EO is relatively atomised, with interoperability made difficult by diverse formats and data structures. If ever larger datasets are to be built, and duplication of ef…
▽ More
Deep learning models are increasingly data-hungry, requiring significant resources to collect and compile the datasets needed to train them, with Earth Observation (EO) models being no exception. However, the landscape of datasets in EO is relatively atomised, with interoperability made difficult by diverse formats and data structures. If ever larger datasets are to be built, and duplication of effort minimised, then a shared framework that allows users to combine and access multiple datasets is needed. Here, Major TOM (Terrestrial Observation Metaset) is proposed as this extensible framework. Primarily, it consists of a geographical indexing system based on a set of grid points and a metadata structure that allows multiple datasets with different sources to be merged. Besides the specification of Major TOM as a framework, this work also presents a large, open-access dataset, MajorTOM-Core, which covers the vast majority of the Earth's land surface. This dataset provides the community with both an immediately useful resource, as well as acting as a template for future additions to the Major TOM ecosystem. Access: https://huggingface.co/Major-TOM
△ Less
Submitted 20 June, 2024; v1 submitted 19 February, 2024;
originally announced February 2024.
-
Factorizing the Brauer monoid in polynomial time
Authors:
Daniele Marchei,
Emanuela Merelli,
Andrew Francis
Abstract:
Finding a minimal factorization for a generic semigroup can be done by using the Froidure-Pin Algorithm, which is not feasible for semigroups of large sizes. On the other hand, if we restrict our attention to just a particular semigroup, we could leverage its structure to obtain a much faster algorithm. In particular, $\mathcal{O}(N^2)$ algorithms are known for factorizing the Symmetric group…
▽ More
Finding a minimal factorization for a generic semigroup can be done by using the Froidure-Pin Algorithm, which is not feasible for semigroups of large sizes. On the other hand, if we restrict our attention to just a particular semigroup, we could leverage its structure to obtain a much faster algorithm. In particular, $\mathcal{O}(N^2)$ algorithms are known for factorizing the Symmetric group $S_N$ and the Temperley-Lieb monoid $\mathcal{T}\mathcal{L}_N$, but none for their superset the Brauer monoid $\mathcal{B}_{N}$. In this paper we hence propose a $\mathcal{O}(N^4)$ factorization algorithm for $\mathcal{B}_{N}$. At each iteration, the algorithm rewrites the input $X \in \mathcal{B}_{N}$ as $X = X' \circ p_i$ such that $\ell(X') = \ell(X) - 1$, where $p_i$ is a factor for $X$ and $\ell$ is a length function that returns the minimal number of factors needed to generate $X$.
△ Less
Submitted 13 February, 2024; v1 submitted 12 February, 2024;
originally announced February 2024.
-
From LAION-5B to LAION-EO: Filtering Billions of Images Using Anchor Datasets for Satellite Image Extraction
Authors:
Mikolaj Czerkawski,
Alistair Francis
Abstract:
Large datasets, such as LAION-5B, contain a diverse distribution of images shared online. However, extraction of domain-specific subsets of large image corpora is challenging. The extraction approach based on an anchor dataset, combined with further filtering, is proposed here and demonstrated for the domain of satellite imagery. This results in the release of LAION-EO, a dataset sourced from the…
▽ More
Large datasets, such as LAION-5B, contain a diverse distribution of images shared online. However, extraction of domain-specific subsets of large image corpora is challenging. The extraction approach based on an anchor dataset, combined with further filtering, is proposed here and demonstrated for the domain of satellite imagery. This results in the release of LAION-EO, a dataset sourced from the web containing pairs of text and satellite images in high (pixel-wise) resolution. The paper outlines the acquisition procedure as well as some of the features of the dataset.
△ Less
Submitted 27 September, 2023;
originally announced September 2023.
-
Principles and Guidelines for Evaluating Social Robot Navigation Algorithms
Authors:
Anthony Francis,
Claudia Pérez-D'Arpino,
Chengshu Li,
Fei Xia,
Alexandre Alahi,
Rachid Alami,
Aniket Bera,
Abhijat Biswas,
Joydeep Biswas,
Rohan Chandra,
Hao-Tien Lewis Chiang,
Michael Everett,
Sehoon Ha,
Justin Hart,
Jonathan P. How,
Haresh Karnan,
Tsang-Wei Edward Lee,
Luis J. Manso,
Reuth Mirksy,
Sören Pirk,
Phani Teja Singamaneni,
Peter Stone,
Ada V. Taylor,
Peter Trautman,
Nathan Tsoi
, et al. (6 additional authors not shown)
Abstract:
A major challenge to deploying robots widely is navigation in human-populated environments, commonly referred to as social robot navigation. While the field of social navigation has advanced tremendously in recent years, the fair evaluation of algorithms that tackle social navigation remains hard because it involves not just robotic agents moving in static environments but also dynamic human agent…
▽ More
A major challenge to deploying robots widely is navigation in human-populated environments, commonly referred to as social robot navigation. While the field of social navigation has advanced tremendously in recent years, the fair evaluation of algorithms that tackle social navigation remains hard because it involves not just robotic agents moving in static environments but also dynamic human agents and their perceptions of the appropriateness of robot behavior. In contrast, clear, repeatable, and accessible benchmarks have accelerated progress in fields like computer vision, natural language processing and traditional robot navigation by enabling researchers to fairly compare algorithms, revealing limitations of existing solutions and illuminating promising new directions. We believe the same approach can benefit social navigation. In this paper, we pave the road towards common, widely accessible, and repeatable benchmarking criteria to evaluate social robot navigation. Our contributions include (a) a definition of a socially navigating robot as one that respects the principles of safety, comfort, legibility, politeness, social competency, agent understanding, proactivity, and responsiveness to context, (b) guidelines for the use of metrics, development of scenarios, benchmarks, datasets, and simulators to evaluate social navigation, and (c) a design of a social navigation metrics framework to make it easier to compare results from different simulators, robots and datasets.
△ Less
Submitted 19 September, 2023; v1 submitted 29 June, 2023;
originally announced June 2023.
-
Retrospectives on the Embodied AI Workshop
Authors:
Matt Deitke,
Dhruv Batra,
Yonatan Bisk,
Tommaso Campari,
Angel X. Chang,
Devendra Singh Chaplot,
Changan Chen,
Claudia Pérez D'Arpino,
Kiana Ehsani,
Ali Farhadi,
Li Fei-Fei,
Anthony Francis,
Chuang Gan,
Kristen Grauman,
David Hall,
Winson Han,
Unnat Jain,
Aniruddha Kembhavi,
Jacob Krantz,
Stefan Lee,
Chengshu Li,
Sagnik Majumder,
Oleksandr Maksymets,
Roberto Martín-Martín,
Roozbeh Mottaghi
, et al. (14 additional authors not shown)
Abstract:
We present a retrospective on the state of Embodied AI research. Our analysis focuses on 13 challenges presented at the Embodied AI Workshop at CVPR. These challenges are grouped into three themes: (1) visual navigation, (2) rearrangement, and (3) embodied vision-and-language. We discuss the dominant datasets within each theme, evaluation metrics for the challenges, and the performance of state-of…
▽ More
We present a retrospective on the state of Embodied AI research. Our analysis focuses on 13 challenges presented at the Embodied AI Workshop at CVPR. These challenges are grouped into three themes: (1) visual navigation, (2) rearrangement, and (3) embodied vision-and-language. We discuss the dominant datasets within each theme, evaluation metrics for the challenges, and the performance of state-of-the-art models. We highlight commonalities between top approaches to the challenges and identify potential future directions for Embodied AI research.
△ Less
Submitted 4 December, 2022; v1 submitted 13 October, 2022;
originally announced October 2022.
-
Learning Model Predictive Controllers with Real-Time Attention for Real-World Navigation
Authors:
Xuesu Xiao,
Tingnan Zhang,
Krzysztof Choromanski,
Edward Lee,
Anthony Francis,
Jake Varley,
Stephen Tu,
Sumeet Singh,
Peng Xu,
Fei Xia,
Sven Mikael Persson,
Dmitry Kalashnikov,
Leila Takayama,
Roy Frostig,
Jie Tan,
Carolina Parada,
Vikas Sindhwani
Abstract:
Despite decades of research, existing navigation systems still face real-world challenges when deployed in the wild, e.g., in cluttered home environments or in human-occupied public spaces. To address this, we present a new class of implicit control policies combining the benefits of imitation learning with the robust handling of system constraints from Model Predictive Control (MPC). Our approach…
▽ More
Despite decades of research, existing navigation systems still face real-world challenges when deployed in the wild, e.g., in cluttered home environments or in human-occupied public spaces. To address this, we present a new class of implicit control policies combining the benefits of imitation learning with the robust handling of system constraints from Model Predictive Control (MPC). Our approach, called Performer-MPC, uses a learned cost function parameterized by vision context embeddings provided by Performers -- a low-rank implicit-attention Transformer. We jointly train the cost function and construct the controller relying on it, effectively solving end-to-end the corresponding bi-level optimization problem. We show that the resulting policy improves standard MPC performance by leveraging a few expert demonstrations of the desired navigation behavior in different challenging real-world scenarios. Compared with a standard MPC policy, Performer-MPC achieves >40% better goal reached in cluttered environments and >65% better on social metrics when navigating around humans.
△ Less
Submitted 23 September, 2022; v1 submitted 22 September, 2022;
originally announced September 2022.
-
Gesture2Path: Imitation Learning for Gesture-aware Navigation
Authors:
Catie Cuan,
Edward Lee,
Emre Fisher,
Anthony Francis,
Leila Takayama,
Tingnan Zhang,
Alexander Toshev,
Sören Pirk
Abstract:
As robots increasingly enter human-centered environments, they must not only be able to navigate safely around humans, but also adhere to complex social norms. Humans often rely on non-verbal communication through gestures and facial expressions when navigating around other people, especially in densely occupied spaces. Consequently, robots also need to be able to interpret gestures as part of sol…
▽ More
As robots increasingly enter human-centered environments, they must not only be able to navigate safely around humans, but also adhere to complex social norms. Humans often rely on non-verbal communication through gestures and facial expressions when navigating around other people, especially in densely occupied spaces. Consequently, robots also need to be able to interpret gestures as part of solving social navigation tasks. To this end, we present Gesture2Path, a novel social navigation approach that combines image-based imitation learning with model-predictive control. Gestures are interpreted based on a neural network that operates on streams of images, while we use a state-of-the-art model predictive control algorithm to solve point-to-point navigation tasks. We deploy our method on real robots and showcase the effectiveness of our approach for the four gestures-navigation scenarios: left/right, follow me, and make a circle. Our experiments indicate that our method is able to successfully interpret complex human gestures and to use them as a signal to generate socially compliant trajectories for navigation tasks. We validated our method based on in-situ ratings of participants interacting with the robots.
△ Less
Submitted 19 September, 2022;
originally announced September 2022.
-
Egret Swarm Optimization Algorithm: An Evolutionary Computation Approach for Model Free Optimization
Authors:
Zuyan Chen,
Adam Francis,
Shuai Li,
Bolin Liao,
Dunhui Xiao
Abstract:
A novel meta-heuristic algorithm, Egret Swarm Optimization Algorithm (ESOA), is proposed in this paper, which is inspired by two egret species' (Great Egret and Snowy Egret) hunting behavior. ESOA consists of three primary components: Sit-And-Wait Strategy, Aggressive Strategy as well as Discriminant Conditions. The performance of ESOA on 36 benchmark functions as well as 2 engineering problems ar…
▽ More
A novel meta-heuristic algorithm, Egret Swarm Optimization Algorithm (ESOA), is proposed in this paper, which is inspired by two egret species' (Great Egret and Snowy Egret) hunting behavior. ESOA consists of three primary components: Sit-And-Wait Strategy, Aggressive Strategy as well as Discriminant Conditions. The performance of ESOA on 36 benchmark functions as well as 2 engineering problems are compared with Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Differential Evolution (DE), Grey Wolf Optimizer (GWO), and Harris Hawks Optimization (HHO). The result proves the superior effectiveness and robustness of ESOA. The source code used in this work can be retrieved from https://github.com/Knightsll/Egret_Swarm_Optimization_Algorithm; https://ww2.mathworks.cn/matlabcentral/fileexchange/115595-egret-swarm-optimization-algorithm-esoa.
△ Less
Submitted 29 July, 2022;
originally announced July 2022.
-
Google Scanned Objects: A High-Quality Dataset of 3D Scanned Household Items
Authors:
Laura Downs,
Anthony Francis,
Nate Koenig,
Brandon Kinman,
Ryan Hickman,
Krista Reymann,
Thomas B. McHugh,
Vincent Vanhoucke
Abstract:
Interactive 3D simulations have enabled breakthroughs in robotics and computer vision, but simulating the broad diversity of environments needed for deep learning requires large corpora of photo-realistic 3D object models. To address this need, we present Google Scanned Objects, an open-source collection of over one thousand 3D-scanned household items released under a Creative Commons license; the…
▽ More
Interactive 3D simulations have enabled breakthroughs in robotics and computer vision, but simulating the broad diversity of environments needed for deep learning requires large corpora of photo-realistic 3D object models. To address this need, we present Google Scanned Objects, an open-source collection of over one thousand 3D-scanned household items released under a Creative Commons license; these models are preprocessed for use in Ignition Gazebo and the Bullet simulation platforms, but are easily adaptable to other simulators. We describe our object scanning and curation pipeline, then provide statistics about the contents of the dataset and its usage. We hope that the diversity, quality, and flexibility of Google Scanned Objects will lead to advances in interactive simulation, synthetic perception, and robotic learning.
△ Less
Submitted 25 April, 2022;
originally announced April 2022.
-
A Protocol for Validating Social Navigation Policies
Authors:
Sören Pirk,
Edward Lee,
Xuesu Xiao,
Leila Takayama,
Anthony Francis,
Alexander Toshev
Abstract:
Enabling socially acceptable behavior for situated agents is a major goal of recent robotics research. Robots should not only operate safely around humans, but also abide by complex social norms. A key challenge for developing socially-compliant policies is measuring the quality of their behavior. Social behavior is enormously complex, making it difficult to create reliable metrics to gauge the pe…
▽ More
Enabling socially acceptable behavior for situated agents is a major goal of recent robotics research. Robots should not only operate safely around humans, but also abide by complex social norms. A key challenge for developing socially-compliant policies is measuring the quality of their behavior. Social behavior is enormously complex, making it difficult to create reliable metrics to gauge the performance of algorithms. In this paper, we propose a protocol for social navigation benchmarking that defines a set of canonical social navigation scenarios and an in-situ metric for evaluating performance on these scenarios using questionnaires. Our experiments show this protocol is realistic, scalable, and repeatable across runs and physical spaces. Our protocol can be replicated verbatim or it can be used to define a social navigation benchmark for novel scenarios. Our goal is to introduce a protocol for benchmarking social scenarios that is homogeneous and comparable.
△ Less
Submitted 29 April, 2022; v1 submitted 11 April, 2022;
originally announced April 2022.
-
SEnSeI: A Deep Learning Module for Creating Sensor Independent Cloud Masks
Authors:
Alistair Francis,
John Mrziglod,
Panagiotis Sidiropoulos,
Jan-Peter Muller
Abstract:
We introduce a novel neural network architecture -- Spectral ENcoder for SEnsor Independence (SEnSeI) -- by which several multispectral instruments, each with different combinations of spectral bands, can be used to train a generalised deep learning model. We focus on the problem of cloud masking, using several pre-existing datasets, and a new, freely available dataset for Sentinel-2. Our model is…
▽ More
We introduce a novel neural network architecture -- Spectral ENcoder for SEnsor Independence (SEnSeI) -- by which several multispectral instruments, each with different combinations of spectral bands, can be used to train a generalised deep learning model. We focus on the problem of cloud masking, using several pre-existing datasets, and a new, freely available dataset for Sentinel-2. Our model is shown to achieve state-of-the-art performance on the satellites it was trained on (Sentinel-2 and Landsat 8), and is able to extrapolate to sensors it has not seen during training such as Landsat 7, PerúSat-1, and Sentinel-3 SLSTR. Model performance is shown to improve when multiple satellites are used in training, approaching or surpassing the performance of specialised, single-sensor models. This work is motivated by the fact that the remote sensing community has access to data taken with a hugely variety of sensors. This has inevitably led to labelling efforts being undertaken separately for different sensors, which limits the performance of deep learning models, given their need for huge training sets to perform optimally. Sensor independence can enable deep learning models to utilise multiple datasets for training simultaneously, boosting performance and making them much more widely applicable. This may lead to deep learning approaches being used more frequently for on-board applications and in ground segment data processing, which generally require models to be ready at launch or soon afterwards.
△ Less
Submitted 16 November, 2021;
originally announced November 2021.
-
Style-based quantum generative adversarial networks for Monte Carlo events
Authors:
Carlos Bravo-Prieto,
Julien Baglio,
Marco Cè,
Anthony Francis,
Dorota M. Grabowska,
Stefano Carrazza
Abstract:
We propose and assess an alternative quantum generator architecture in the context of generative adversarial learning for Monte Carlo event generation, used to simulate particle physics processes at the Large Hadron Collider (LHC). We validate this methodology by implementing the quantum network on artificial data generated from known underlying distributions. The network is then applied to Monte…
▽ More
We propose and assess an alternative quantum generator architecture in the context of generative adversarial learning for Monte Carlo event generation, used to simulate particle physics processes at the Large Hadron Collider (LHC). We validate this methodology by implementing the quantum network on artificial data generated from known underlying distributions. The network is then applied to Monte Carlo-generated datasets of specific LHC scattering processes. The new quantum generator architecture leads to a generalization of the state-of-the-art implementations, achieving smaller Kullback-Leibler divergences even with shallow-depth networks. Moreover, the quantum generator successfully learns the underlying distribution functions even if trained with small training sample sets; this is particularly interesting for data augmentation applications. We deploy this novel methodology on two different quantum hardware architectures, trapped-ion and superconducting technologies, to test its hardware-independent viability.
△ Less
Submitted 6 August, 2022; v1 submitted 13 October, 2021;
originally announced October 2021.
-
Algorithmic techniques for finding resistance distances on structured graphs
Authors:
E. J. Evans,
A. E. Francis
Abstract:
In this paper we give a survey of methods used to calculate values of resistance distance (also known as effective resistance) in graphs. Resistance distance has played a prominent role not only in circuit theory and chemistry, but also in combinatorial matrix theory and spectral graph theory. Moreover resistance distance has applications ranging from quantifying biological structures, distributed…
▽ More
In this paper we give a survey of methods used to calculate values of resistance distance (also known as effective resistance) in graphs. Resistance distance has played a prominent role not only in circuit theory and chemistry, but also in combinatorial matrix theory and spectral graph theory. Moreover resistance distance has applications ranging from quantifying biological structures, distributed control systems, network analysis, and power grid systems. In this paper we discuss both exact techniques and approximate techniques and for each method discussed we provide an illustrative example of the technique. We also present some open questions and conjectures.
△ Less
Submitted 13 September, 2021; v1 submitted 17 August, 2021;
originally announced August 2021.
-
Reversible Colour Density Compression of Images using cGANs
Authors:
Arun Jose,
Abraham Francis
Abstract:
Image compression using colour densities is historically impractical to decompress losslessly. We examine the use of conditional generative adversarial networks in making this transformation more feasible, through learning a mapping between the images and a loss function to train on. We show that this method is effective at producing visually lossless generations, indicating that efficient colour…
▽ More
Image compression using colour densities is historically impractical to decompress losslessly. We examine the use of conditional generative adversarial networks in making this transformation more feasible, through learning a mapping between the images and a loss function to train on. We show that this method is effective at producing visually lossless generations, indicating that efficient colour compression is viable.
△ Less
Submitted 19 June, 2021;
originally announced June 2021.
-
Graph Neural Networks for Motion Planning
Authors:
Arbaaz Khan,
Alejandro Ribeiro,
Vijay Kumar,
Anthony G. Francis
Abstract:
This paper investigates the feasibility of using Graph Neural Networks (GNNs) for classical motion planning problems. We propose guiding both continuous and discrete planning algorithms using GNNs' ability to robustly encode the topology of the planning space using a property called permutation invariance. We present two techniques, GNNs over dense fixed graphs for low-dimensional problems and sam…
▽ More
This paper investigates the feasibility of using Graph Neural Networks (GNNs) for classical motion planning problems. We propose guiding both continuous and discrete planning algorithms using GNNs' ability to robustly encode the topology of the planning space using a property called permutation invariance. We present two techniques, GNNs over dense fixed graphs for low-dimensional problems and sampling-based GNNs for high-dimensional problems. We examine the ability of a GNN to tackle planning problems such as identifying critical nodes or learning the sampling distribution in Rapidly-exploring Random Trees (RRT). Experiments with critical sampling, a pendulum and a six DoF robot arm show GNNs improve on traditional analytic methods as well as learning approaches using fully-connected or convolutional neural networks.
△ Less
Submitted 14 December, 2020; v1 submitted 11 June, 2020;
originally announced June 2020.
-
Evolving Rewards to Automate Reinforcement Learning
Authors:
Aleksandra Faust,
Anthony Francis,
Dar Mehta
Abstract:
Many continuous control tasks have easily formulated objectives, yet using them directly as a reward in reinforcement learning (RL) leads to suboptimal policies. Therefore, many classical control tasks guide RL training using complex rewards, which require tedious hand-tuning. We automate the reward search with AutoRL, an evolutionary layer over standard RL that treats reward tuning as hyperparame…
▽ More
Many continuous control tasks have easily formulated objectives, yet using them directly as a reward in reinforcement learning (RL) leads to suboptimal policies. Therefore, many classical control tasks guide RL training using complex rewards, which require tedious hand-tuning. We automate the reward search with AutoRL, an evolutionary layer over standard RL that treats reward tuning as hyperparameter optimization and trains a population of RL agents to find a reward that maximizes the task objective. AutoRL, evaluated on four Mujoco continuous control tasks over two RL algorithms, shows improvements over baselines, with the the biggest uplift for more complex tasks. The video can be found at: \url{https://youtu.be/svdaOFfQyC8}.
△ Less
Submitted 18 May, 2019;
originally announced May 2019.
-
Long-Range Indoor Navigation with PRM-RL
Authors:
Anthony Francis,
Aleksandra Faust,
Hao-Tien Lewis Chiang,
Jasmine Hsu,
J. Chase Kew,
Marek Fiser,
Tsang-Wei Edward Lee
Abstract:
Long-range indoor navigation requires guiding robots with noisy sensors and controls through cluttered environments along paths that span a variety of buildings. We achieve this with PRM-RL, a hierarchical robot navigation method in which reinforcement learning agents that map noisy sensors to robot controls learn to solve short-range obstacle avoidance tasks, and then sampling-based planners map…
▽ More
Long-range indoor navigation requires guiding robots with noisy sensors and controls through cluttered environments along paths that span a variety of buildings. We achieve this with PRM-RL, a hierarchical robot navigation method in which reinforcement learning agents that map noisy sensors to robot controls learn to solve short-range obstacle avoidance tasks, and then sampling-based planners map where these agents can reliably navigate in simulation; these roadmaps and agents are then deployed on robots, guiding them along the shortest path where the agents are likely to succeed. Here we use Probabilistic Roadmaps (PRMs) as the sampling-based planner, and AutoRL as the reinforcement learning method in the indoor navigation context. We evaluate the method in simulation for kinematic differential drive and kinodynamic car-like robots in several environments, and on differential-drive robots at three physical sites. Our results show PRM-RL with AutoRL is more successful than several baselines, is robust to noise, and can guide robots over hundreds of meters in the face of noise and obstacles in both simulation and on robots, including over 5.8 kilometers of physical robot navigation. Video: https://youtu.be/xN-OWX5gKvQ
△ Less
Submitted 22 February, 2020; v1 submitted 25 February, 2019;
originally announced February 2019.
-
Learning Navigation Behaviors End-to-End with AutoRL
Authors:
Hao-Tien Lewis Chiang,
Aleksandra Faust,
Marek Fiser,
Anthony Francis
Abstract:
We learn end-to-end point-to-point and path-following navigation behaviors that avoid moving obstacles. These policies receive noisy lidar observations and output robot linear and angular velocities. The policies are trained in small, static environments with AutoRL, an evolutionary automation layer around Reinforcement Learning (RL) that searches for a deep RL reward and neural network architectu…
▽ More
We learn end-to-end point-to-point and path-following navigation behaviors that avoid moving obstacles. These policies receive noisy lidar observations and output robot linear and angular velocities. The policies are trained in small, static environments with AutoRL, an evolutionary automation layer around Reinforcement Learning (RL) that searches for a deep RL reward and neural network architecture with large-scale hyper-parameter optimization. AutoRL first finds a reward that maximizes task completion, and then finds a neural network architecture that maximizes the cumulative of the found reward. Empirical evaluations, both in simulation and on-robot, show that AutoRL policies do not suffer from the catastrophic forgetfulness that plagues many other deep reinforcement learning algorithms, generalize to new environments and moving obstacles, are robust to sensor, actuator, and localization noise, and can serve as robust building blocks for larger navigation tasks. Our path-following and point-to-point policies are respectively 23% and 26% more successful than comparison methods across new environments. Video at: https://youtu.be/0UwkjpUEcbI
△ Less
Submitted 1 February, 2019; v1 submitted 26 September, 2018;
originally announced September 2018.
-
PRM-RL: Long-range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-based Planning
Authors:
Aleksandra Faust,
Oscar Ramirez,
Marek Fiser,
Kenneth Oslund,
Anthony Francis,
James Davidson,
Lydia Tapia
Abstract:
We present PRM-RL, a hierarchical method for long-range navigation task completion that combines sampling based path planning with reinforcement learning (RL). The RL agents learn short-range, point-to-point navigation policies that capture robot dynamics and task constraints without knowledge of the large-scale topology. Next, the sampling-based planners provide roadmaps which connect robot confi…
▽ More
We present PRM-RL, a hierarchical method for long-range navigation task completion that combines sampling based path planning with reinforcement learning (RL). The RL agents learn short-range, point-to-point navigation policies that capture robot dynamics and task constraints without knowledge of the large-scale topology. Next, the sampling-based planners provide roadmaps which connect robot configurations that can be successfully navigated by the RL agent. The same RL agents are used to control the robot under the direction of the planning, enabling long-range navigation. We use the Probabilistic Roadmaps (PRMs) for the sampling-based planner. The RL agents are constructed using feature-based and deep neural net policies in continuous state and action spaces. We evaluate PRM-RL, both in simulation and on-robot, on two navigation tasks with non-trivial robot dynamics: end-to-end differential drive indoor navigation in office environments, and aerial cargo delivery in urban environments with load displacement constraints. Our results show improvement in task completion over both RL agents on their own and traditional sampling-based planners. In the indoor navigation task, PRM-RL successfully completes up to 215 m long trajectories under noisy sensor conditions, and the aerial cargo delivery completes flights over 1000 m without violating the task constraints in an environment 63 million times larger than used in training.
△ Less
Submitted 16 May, 2018; v1 submitted 11 October, 2017;
originally announced October 2017.
-
Tree-based unrooted phylogenetic networks
Authors:
Andrew Francis,
Katharina Huber,
Vincent Moulton
Abstract:
Phylogenetic networks are a generalization of phylogenetic trees that are used to represent non-tree-like evolutionary histories that arise in organisms such as plants and bacteria, or uncertainty in evolutionary histories. An \emph{unrooted} phylogenetic network on a nonempty, finite set $X$ of taxa, or \emph{network}, is a connected graph in which every vertex has degree 1 or 3 and whose leaf-se…
▽ More
Phylogenetic networks are a generalization of phylogenetic trees that are used to represent non-tree-like evolutionary histories that arise in organisms such as plants and bacteria, or uncertainty in evolutionary histories. An \emph{unrooted} phylogenetic network on a nonempty, finite set $X$ of taxa, or \emph{network}, is a connected graph in which every vertex has degree 1 or 3 and whose leaf-set is $X$. It is called a \emph{phylogenetic tree} if the underlying graph is a tree. In this paper we consider properties of \emph{tree-based networks}, that is, networks that can be constructed by adding edges into a phylogenetic tree. We show that although they have some properties in common with their rooted analogues which have recently drawn much attention in the literature, they have some striking differences in terms of both their structural and computational properties. We expect that our results could eventually have applications to, for example, detecting horizontal gene transfer or hyrbridization which are important factors in the evolution of many organisms.
△ Less
Submitted 7 December, 2017; v1 submitted 6 April, 2017;
originally announced April 2017.
-
Which phylogenetic networks are merely trees with additional arcs?
Authors:
Andrew R. Francis,
Mike Steel
Abstract:
A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on `2-SAT') that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist…
▽ More
A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on `2-SAT') that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion.
△ Less
Submitted 21 May, 2015; v1 submitted 24 February, 2015;
originally announced February 2015.
-
Curve Shortening and the Rendezvous Problem for Mobile Autonomous Robots
Authors:
Stephen L. Smith,
Mireille E. Broucke,
Bruce A. Francis
Abstract:
If a smooth, closed, and embedded curve is deformed along its normal vector field at a rate proportional to its curvature, it shrinks to a circular point. This curve evolution is called Euclidean curve shortening and the result is known as the Gage-Hamilton-Grayson Theorem. Motivated by the rendezvous problem for mobile autonomous robots, we address the problem of creating a polygon shortening f…
▽ More
If a smooth, closed, and embedded curve is deformed along its normal vector field at a rate proportional to its curvature, it shrinks to a circular point. This curve evolution is called Euclidean curve shortening and the result is known as the Gage-Hamilton-Grayson Theorem. Motivated by the rendezvous problem for mobile autonomous robots, we address the problem of creating a polygon shortening flow. A linear scheme is proposed that exhibits several analogues to Euclidean curve shortening: The polygon shrinks to an elliptical point, convex polygons remain convex, and the perimeter of the polygon is monotonically decreasing.
△ Less
Submitted 16 May, 2006;
originally announced May 2006.