This paper presents a cognitive map (CM) model fused with a histogram-based reactive local navigator algorithm for real-time robot mapping and navigation. Drawing inspiration from biological navigation, the CM model integrates elements like landmarks, Euclidean distance, exploratory movement, and reward-driven actions. Key features of the model include types of cognitive mapping cells designed to replicate their biological functions in a computationally efficient manner. Built on cognitive map concepts used to explain mammalian navigation, this CM model enables robots to navigate complex environments without needing complete environmental exploration. Additionally, an enhanced ℬ-spline curve scheme ensures a smoother, safer trajectory. After planning a global route, the model utilizes a histogram-based local navigation algorithm to dynamically avoid obstacles while creating real-time maps as the robot follows its path. Simulation and comparison results validate that this integrated approach supports real-time navigation and mapping in unknown environments, offering significant improvements in robotic spatial navigation and real-time map building.

Identifying spatially complete planar primitives from visual data is a crucial task in computer vision. Prior methods are largely restricted to either 2D segment recovery or simplifying 3D structures, even with extensive plane annotations. We present PlanarNeRF, a novel framework capable of detecting dense 3D planes through online learning. Drawing upon the neural field representation, PlanarNeRF brings three major contributions. First, it enhances 3D plane detection with concurrent appearance and geometry knowledge. Second, a lightweight plane fitting module is used to estimate plane parameters. Third, a novel global memory bank structure with an update mechanism is introduced, ensuring consistent cross-frame correspondence. The flexible architecture of PlanarNeRF allows it to function in both 2D-supervised and self-supervised solutions, in each of which it can effectively learn from sparse training signals, significantly improving training efficiency. Through extensive experiments, we demonstrate the effectiveness of PlanarNeRF in various real-world scenarios and remarkable improvement in 3D plane detection over existing works.

With the increasing use of autonomous robots and vehicles in unfamiliar environments, image-based navigation and localization have gained significant attention. Some advanced algorithms address robust and efficient global path planning. However, reliable local reactive navigation is crucial for obstacle avoidance in close proximity. This paper introduces a biologically inspired neural networks (BNN) model with a dynamic moving window method (DMWM) for local navigation, complemented by a bio-inspired Bat algorithm (BA) for global path planning. The BA utilizes visual features extracted from images using convolutional neural networks (CNNs) to generate paths for autonomous robots. This paper outlines the requirements for image-based navigation, addresses the BA’s principles and its suitability for global path planning, and details the development of the BNN with DMWM for local navigation. Finally, simulations and comparative studies validate the performance and reliability of the proposed methods.

The classical Model Predictive Path Integral (MPPI) control framework, while effective in many applications, lacks reliable safety features since it relies due to its reliance on arisk-neutraltrajectory evaluation technique, which can present challenges for safety-critical applications such as autonomous driving. Furthermore, if when the majority of MPPI sampled trajectories concentrate in high-cost regions, it may generate aninfeasiblecontrol sequence. To address this challenge, we propose the U-MPPI control strategy, a novel methodology that can effectively manage system uncertainties while integrating a more efficient trajectory sampling strategy. The core concept is to leverage the Unscented Transform (UT) to propagate not only the mean but also the covariance of the system dynamics, going beyond the traditional MPPI method. As a result, it introduces a novel and more efficient trajectory sampling strategy, significantly enhancing state-space exploration and ultimately reducing the risk of being trapped in local minima. Furthermore, by leveraging the uncertainty information provided by UT, we incorporate arisk-sensitivecost function that explicitly accounts for risk or uncertainty throughout the trajectory evaluation process, resulting in a more resilient control system capable of handling uncertain conditions. By conducting extensive simulations of 2D aggressive autonomous navigation in both known and unknown cluttered environments, we verify the efficiency and robustness of our proposed U-MPPI control strategy compared to the baseline MPPI. We further validate the practicality of U-MPPI through real-world demonstrations in unknown cluttered environments, showcasing its superior ability to incorporate both the UT and local costmap into the optimization problem without introducing additional complexity.

We propose a new method for autonomous navigation in uneven terrains by utilizing a sparse Gaussian Process (SGP) based local perception model. The SGP local perception model is trained on local ranging observation (pointcloud) to learn the terrain elevation profile and extract the feasible navigation subgoals around the robot. Subsequently, a cost function, which prioritizes the safety of the robot in terms of keeping the robot’s roll and pitch angles bounded within a specified range, is used to select a safety-aware subgoal that leads the robot to its final destination. The algorithm is designed to run in real-time and is intensively evaluated in simulation and real-world experiments. The results compellingly demonstrate that our proposed algorithm consistently navigates uneven terrains with high efficiency and surpasses the performance of other planners. The implementation of our method, including the supplementary video showing the experimental and real-world results, is available at https://rb.gy/3ov2r8.

Efficient navigation through uneven terrain remains a challenging endeavor for autonomous robots. We propose a new geometric-based uneven terrain mapless navigation framework combining a Sparse Gaussian Process (SGP) local map with a Rapidly-Exploring Random Tree* (RRT*) planner. Our approach begins with the generation of a high-resolution SGP local map, providing an interpolated representation of the robot’s immediate environment. This map captures crucial environmental variations, including height, uncertainties, and slope characteristics. Subsequently, we construct a traversability map based on the SGP representation to guide our planning process. The RRT* planner efficiently generates real-time navigation paths, avoiding untraversable terrain in pursuit of the goal. This combination of SGP-based terrain interpretation and RRT* planning enables ground robots to safely navigate environments with varying elevations and steep obstacles. We evaluate the performance of our proposed approach through robust simulation testing, highlighting its effectiveness in achieving safe and efficient navigation compared to existing methods. See the project GitHub1for source code and supplementary materials, including a video demonstrating experimental results.

Autonomous navigation in unknown environments is challenging and requires the consideration of both geometric and semantic information to assess the navigability of the environment. In this work, we propose a novel space modeling framework, Visual-Geometry Sparse Gaussian Process (VG-SGP), that simultaneously considers the semantics and geometry of the scene. Our proposed approach can overcome the limitation of visual planners that fail to recognize geometry associated with the semantic and the geometric planners that completely overlook the semantic information which is very critical in real-world navigation. The proposed method leverages dual Sparse Gaussian Processes in an integrated manner; the first is trained to forecast geometrically navigable spaces while the second predicts the semantically navigable areas. This integrated model is able to pinpoint the overlapping (geometric and semantic) navigable space. The simulation and real-world experiments demonstrate that the proposed VG-SGP model, coupled with our innovative navigation strategy, outperforms models solely reliant on visual or geometric navigation algorithms, highlighting a superior adaptive behavior. We provided a demonstration video1and open-sourced our code2.

Prediction beyond partial observations is crucial for robots to navigate in unknown environments because it can provide extra information regarding the surroundings beyond the current sensing range or resolution. In this work, we consider the inpainting of semantic Bird’s-Eye-View maps. We propose SePaint, an inpainting model for semantic data based on generative multinomial diffusion. To maintain semantic consistency, we need to condition the prediction for the missing regions on the known regions. We propose a novel and efficient condition strategy, Look-Back Condition (LB-Con), which performs one-step look-back operations during the reverse diffusion process. By doing so, we are able to strengthen the harmonization between unknown and known parts, leading to better completion performance. We have conducted extensive experiments on different datasets, showing our proposed model outperforms commonly used interpolation methods in various robotic applications.

Bounded rational agents often make decisions by evaluating a finite selection of choices, typically derived from a reference point termed the ‘default policy,’ based on previous experience. However, the inherent rigidity of the static default policy presents significant challenges for agents when operating in unknown environment, that are not included in agent’s prior knowledge. In this work, we introduce a context-generative default policy that leverages the region observed by the robot to predict unobserved part of the environment, thereby enabling the robot to adaptively adjust its default policy based on both the actual observed map and the imagined unobserved map. Furthermore, the adaptive nature of the bounded rationality framework enables the robot to manage unreliable or incorrect imaginations by selectively sampling a few trajectories in the vicinity of the default policy. Our approach utilizes a diffusion model for map prediction and a sampling-based planning with B-spline trajectory optimization to generate the default policy. Extensive evaluations reveal that the context-generative policy outperforms the baseline methods in identifying and avoiding unseen obstacles. Additionally, real-world experiments conducted with the Crazyflie drones demonstrate the adaptability of our proposed method, even when acting in environments outside the domain of the training distribution.

Virtual Reality (VR) headsets allow users to interact with the virtual world. However, the device physically blocks visual connections among users, causing huge inconveniences for VR meetings. To address this issue, studies have been conducted to restore human faces from images captured by Headset Mounted Cameras (HMC). Unfortunately, existing approaches heavily rely on high-resolution person-specific 3D models which are prohibitively expensive to apply to large-scale scenarios. Our goal is to design an efficient framework for restoring users’ facial data in VR meetings. Specifically, we first build a new dataset, named Facial Image Composition (FIC) data which approximates the real HMC images from a VR headset. By leveraging the heterogeneity of the HMC images, we decompose the restoration problem into a local geometry transformation and global color/style fusion. Then we propose a 2D light-weight facial image composition network (FIC-Net), where three independent local models are responsible for transforming raw HMC patches and the global model performs a fusion of the transformed HMC patches with a pre-recorded reference image. Finally, we also propose a stage-wise training strategy to optimize the generalization of our FIC-Net. We have validated the effectiveness of our proposed FIC-Net through extensive experiments.

This paper presents a framework to represent high-fidelity pointcloud sensor observations for efficient communication and storage. The proposed approach exploits Sparse Gaussian Process to encode pointcloud into a compact form. Our approach represents both the free space and the occupied space using only one model (one 2D Sparse Gaussian Process) instead of the existing two-model framework (two 3D Gaussian Mixture Models). We achieve this by proposing a variance-based sampling technique that effectively discriminates between the free and occupied space. The new representation requires less memory footprint and can be transmitted across limited-bandwidth communication channels. The framework is extensively evaluated in simulation and it is also demonstrated using a real mobile robot equipped with a 3D LiDAR. Our method results in a 70~100 times reduction in the communication rate compared to sending the raw pointcloud. We have provided a demonstration video11Video: https://youtu.be/BQZzXiCFGrM and open-sourced our code22Code: https://github.com/mahmoud-a-ali/vsgp_pcl.

We propose a new frontier concept called the Gaussian Process Frontier (GP-Frontier) that can be used to locally navigate a robot towards a goal without building a map. The GP-Frontier is built on the uncertainty assessment of an efficient variant of sparse Gaussian Process. Based only on local ranging sensing measurement, the GP-Frontier can be used for navigation in both known and unknown environments. The proposed method is validated through intensive evaluations, and the results show that the GP-Frontier can navigate the robot in a safe and persistent way, i.e., the robot moves in the most open space (thus reducing the risk of collision) without relying on a map or a path planner. A supplementary video that demonstrates the robot navigation behavior is available at https://youtu.be/ndpqTNYqGfw.

Existing multi-agent perception systems assume that every agent utilizes the same model with identical parameters and architecture. The performance can be degraded with different perception models due to the mismatch in their confidence scores. In this work, we propose a model-agnostic multi-agent perception framework to reduce the negative effect caused by the model discrepancies without sharing the model information. Specifically, we propose a confidence calibrator that can eliminate the prediction confidence score bias. Each agent performs such calibration independently on a standard public database to protect intellectual property. We also propose a corresponding bounding box aggregation algorithm that considers the confidence scores and the spatial agreement of neighboring boxes. Our experiments shed light on the necessity of model calibration across different agents, and the results show that the proposed framework improves the baseline 3D object detection performance of heterogeneous agents. The code can be found at this url.

Robot data collected in complex real-world scenarios are often biased due to safety concerns, human preferences, and mission or platform constraints. Consequently, robot learning from such observational data poses great challenges for accurate parameter estimation. We propose a principled causal inference framework for robots to learn the parameters of a stochastic motion model using observational data. Specifically, we leverage the de-biasing functionality of the potential-outcome causal inference framework, the Inverse Propensity Weighting (IPW), and the Doubly Robust (DR) methods, to obtain a better parameter estimation of the robot's stochastic motion model. The IPW is a re-weighting approach to ensure unbiased estimation, and the DR approach further combines any two estimators to strengthen the unbiased result even if one of these estimators is biased. We then develop an approximate policy iteration algorithm using the bias-eliminated estimated state transition function. We validate our framework using both simulation and real-world experiments, and the results have revealed that the proposed causal inference-based navigation and control framework can correctly and efficiently learn the parameters from biased observational data.

Mixup-based data augmentation has been validated to be a critical stage in the self-training framework for unsupervised domain adaptive semantic segmentation (UDASS), which aims to transfer knowledge from a well-annotated (source) domain to an unlabeled (target) domain. Existing self-training methods usually adopt the popular region-based mixup techniques with a random sampling strategy, which unfortunately ignores the dynamic evolution of different semantics across various domains as training proceeds. To improve the UDA-SS performance, we propose an Informed Domain Adaptation (IDA) model, a self-training framework that mixes the data based on class-level segmentation performance, which aims to emphasize small-region semantics during mixup. In our IDA model, the class-level performance is tracked by an expected confidence score (ECS). We then use a dynamic schedule to determine the mixing ratio for data in different domains. Extensive experimental results reveal that our proposed method is able to outperform the state-of-the-art UDA-SS method by a margin of 1.1 mIoU in the adaptation of GTA-V to Cityscapes and of 0.9 mIoU in the adaptation of SYNTHIA to Cityscapes. Code link: https://github.com/ArlenCHEN/IDA.git

Robotic navigation in unknown, cluttered environ-ments with limited sensing capabilities poses significant chal-lenges in robotics. Local trajectory optimization methods, such as Model Predictive Path Intergal (MPPI), are a promising solution to this challenge. However, global guidance is required to ensure effective navigation, especially when encountering challenging environmental conditions or navigating beyond the planning horizon. This study presents the GP-MPPI, an online learning-based control strategy that integrates MPPI with a local perception model based on Sparse Gaussian Process (SGP). The key idea is to leverage the learning capability of SGP to construct a variance (uncertainty) surface, which enables the robot to learn about the navigable space surrounding it, identify a set of suggested subgoals, and ultimately recommend the optimal subgoal that minimizes a predefined cost function to the local MPPI planner. Afterward, MPPI computes the optimal control sequence that satisfies the robot and collision avoidance constraints. Such an approach eliminates the necessity of a global map of the environment or an offline training process. We validate the efficiency and robustness of our proposed control strategy through both simulated and real-world experiments of 2D autonomous navigation tasks in complex unknown en-vironments, demonstrating its superiority in guiding the robot safely towards its desired goal while avoiding obstacles and escaping entrapment in local minima. The GPU implementation of GP-MPPI, including the supplementary video, is available at https://github.com/IhabMohamed/GP-MPPI.

Biological agents, such as humans and animals, are capable of making decisions out of a very large number of choices in a limited time. They can do so because they use their prior knowledge to find a solution that is not necessarily optimal but good enough for the given task. In this work, we study the motion coordination of multiple drones under the above-mentioned paradigm, Bounded Rationality (BR), to achieve cooperative motion planning tasks. Specifically, we design a prior policy that provides useful goal-directed navigation heuristics in familiar environments and is adaptive in unfamiliar ones via Reinforcement Learning augmented with an environment-dependent exploration noise. Integrating this prior policy in the game-theoretic bounded rationality framework allows agents to quickly make decisions in a group considering other agents' computational constraints. Our investigation assures that agents with a well-informed prior policy increase the efficiency of the collective decision-making capability of the group. We have conducted rigorous experiments in simulation and in the real world to demonstrate that the ability of informed agents to navigate to the goal safely can guide the group to coordinate efficiently under the BR framework.

Informative planning seeks a sequence of actions that guide the robot to collect the most informative data to build a large-scale environmental model or learn a dynamical system. Existing work in informative planning mainly focuses on proposing new planners and applying them to various robotic applications such as environmental monitoring, autonomous exploration, and system identification. The informative planners optimize an objective given by a probabilistic model, e.g., Gaussian process regression (GPR). In practice, the ubiquitous sensing outliers can easily affect the model, resulting in a misleading objective. A straightforward solution is to filter out the outliers in the sensing data stream using an off-the-shelf outlier detector. However, informative samples are also scarce by definition so they might be falsely filtered out. In this paper, we propose a method to enable the robot to re-visit the locations where outliers were sampled besides optimizing the informative planning objective. The robot can collect more samples in the vicinity of outliers and update the outlier detector to reduce the number of false alarms. We achieve this by designing a new objective for the Pareto Monte Carlo tree search (MCTS). We demonstrate that the proposed framework performs better than applying an outlier detector naively.

We propose a novel hybrid system (both hardware and software) of an Unmanned Aerial Vehicle (UAV) carrying a miniature Unmanned Ground Vehicle (miniUGV) to perform a complex search and manipulation task. This system leverages the heterogeneous robots to accomplish a task that cannot be done using a single robot system. It enables the UAV to explore a hidden space with a narrow opening through which the miniUGV can easily enter and escape. The hidden space is assumed to be navigable for the miniUGV. The miniUGV uses Infrared (IR) sensors and a monocular camera to search an object in the hidden space. The proposed system takes advantage of a wider field of view (fov) of camera as well as the stochastic nature of the object detection algorithms to guide the miniUGV in the hidden space to find the object. Upon finding the object the miniUGV grabs it using visual servoing and then returns back to its start point from where the UAV retracts it back and transports the object to a safe place. In case there is no object found in the hidden space, UAV continues the aerial search. The tethered miniUGV gives the UAV an ability to act beyond its reach and perform a search and manipulation task which was not possible before for any of the robots individually. The system has a wide range of applications and we have demonstrated its feasibility through repetitive experiments.

In many autonomous mapping tasks, the maps cannot be accurately constructed due to various reasons such as sparse, noisy, and partial sensor measurements. We propose a novel map prediction method built upon recent success of Low-Rank Matrix Completion. The proposed map prediction is able to achieve both map interpolation and extrapolation on raw poor-quality maps with missing or noisy observations. We validate with extensive simulated experiments that the approach can achieve real-time computation for large maps, and the performance is superior to state-of-the-art map prediction approach — Bayesian Hilbert Mapping in terms of mapping accuracy and computation time. Then we demonstrate that with the proposed real-time map prediction framework, the coverage convergence rate (per action step) for a set of representative coverage planning methods commonly used for environmental modeling and monitoring tasks can be significantly improved.

We investigate the autonomous navigation of a mobile robot in the presence of other moving vehicles under time-varying uncertain environmental disturbances. We first predict the future state distributions of other vehicles to account for their uncertain behaviors affected by the time-varying disturbances. We then construct a dynamic-obstacle-aware reachable space that contains states with high probabilities to be reached by the robot, within which the optimal policy is searched. Since, in general, the dynamics of both the vehicle and the environmental disturbances are nonlinear, we utilize a nonlinear Gaussian filter – the unscented transform – to approximate the future state distributions. Finally, the forward reachable space computation and backward policy search are iterated until convergence. Extensive simulation evaluations have revealed significant advantages of this proposed method in terms of computation time, decision accuracy, and planning reliability.

A new mechanism for efficiently solving the Markov decision processes (MDPs) is proposed in this paper. We introduce the notion of reachability landscape where we use the Mean First Passage Time (MFPT) as a means to characterize the reachability of every state in the state space. We show that such reachability characterization very well assesses the importance of states and thus provides a natural basis for effectively prioritizing states and approximating policies. Built on such a novel observation, we design two new algorithms - Mean First Passage Time based Value Iteration (MFPT-VI) and Mean First Passage Time based Policy Iteration (MFPT-PI) - that have been modified from the state-of-the-art solution methods. To validate our design, we have performed numerical evaluations in robotic decision-making scenarios, by comparing the proposed new methods with corresponding classic baseline mechanisms. The evaluation results showed that MFPT-VI and MFPT-PI have outperformed the state-of-the-art solutions in terms of both practical runtime and number of iterations. Aside from the advantage of fast convergence, this new solution method is intuitively easy to understand and practically simple to implement.

We propose a hybrid approach aimed at improving the sample efficiency in goal-directed reinforcement learning. We do this via a two-step mechanism where firstly, we approximate a model from Model-Free reinforcement learning. Then, we leverage this approximate model along with a notion of reachability using Mean First Passage Times to perform Model-Based reinforcement learning. Built on such a novel observation, we design two new algorithms - Mean First Passage Time based Q-Learning (MFPT-Q)and Mean First Passage Time based DYNA (MFPT-DYNA), that have been fundamentally modified from the state-of-the-art reinforcement learning techniques. Preliminary results have shown that our hybrid approaches converge with much fewer iterations than their corresponding state-of-the-art counterparts and therefore requiring much fewer samples and much fewer training trials to converge.

A big challenge in environmental monitoring is the spatiotemporal variation of the phenomena to be observed. To enable persistent sensing and estimation in such a setting, it is beneficial to have a time-varying underlying environmental model. Here we present a planning and learning method that enables an autonomous marine vehicle to perform persistent ocean monitoring tasks by learning and refining an environmental model. To alleviate the computational bottleneck caused by large-scale data accumulated, we propose a framework that iterates between a planning component aimed at collecting the most information-rich data, and a sparse Gaussian Process learning component where the environmental model and hyperparameters are learned online by taking advantage of only a subset of data that provides the greatest contribution. Our simulations with ground-truth ocean data shows that the proposed method is both accurate and efficient.

We consider an orienteering problem (OP) where an agent needs to visit a series (possibly a subset) of depots, from which the maximal accumulated profits are desired within given limited time budget. Different from most existing works where the profits are assumed to be static, in this work we investigate a variant that has arbitrary time-dependent profits. Specifically, the profits to be collected change over time and they follow different (e.g., independent) time-varying functions. The problem is of inherent nonlinearity and difficult to solve by existing methods. To tackle the challenge, we present a simple and effective framework that incorporates time-variations into the fundamental planning process. Specifically, we propose a deterministic spatio-temporal representation where both spatial description and temporal logic are unified into one routing topology. By employing existing basic sorting and searching algorithms, the routing solutions can be computed in an extremely efficient way. The proposed method is easy to implement and extensive numerical results show that our approach is time efficient and generates near-optimal solutions.

This paper presents a fast approximate multi-agent decision theoretic planning method extended from the well-known Markov Decision Process (MDP). Our objective is to plan motions for a team of homogeneous micro air vehicles (MAVs) toward a set of goals, such that each MAV at any state at any moment follows an action policy toward a unique goal, while considering action uncertainty. We pursue an efficient formulation by first considering a deterministic abstraction of the stochastic system based on approximate initial paths. These deterministic and decoupled sub-problems are converted to the stochastic domain and improved by individual agents or a subset of agents. The resulting decoupled formulation requires processing of a partial state space and enables online operation given applications with emerging tasks.

We propose an efficient path planning method for an autonomous underwater vehicle (AUV) used for the long-range and long-term ocean monitoring. We consider both the spatio-temporal variations of ocean phenomena and the disturbances caused by ocean currents, and design an approach integrating the information-theoretic and decision-theoretic planning frameworks. Specifically, the information-theoretic component employs a hierarchical structure and plans the most informative observation way-points for reducing the uncertainty of ocean phenomena modeling and prediction; whereas the decision-theoretic component plans local motions by taking into account the non-stationary ocean current disturbances. We validated the method through simulations with real ocean data.

In scenarios in which new robots and tasks are added to a network of already deployed, interchangeable robots, a trade-off arises in minimizing the cost to execute the tasks and the level of disruption to the system. This paper considers a navigation-oriented variant of this problem and proposes a parametrizable method to adjust the optimization criterion: from minimizing global travel time (or energy, or distance), to minimizing interruption (i.e., obtaining the fewest number of robot reassignments), and mixtures in-between. Paths are computed by a task-allocation formulation in which the destinations of newly deployed robots are added to an existing allocation. We adapt the graph matching variant of the Hungarian algorithm-originally designed to solve the optimal assignment problem in complete graphs-to construct routing paths by showing that there is an interpretation of the sparse Hungarian bipartite graph in three dimensions. When new agent-task pairs are inserted, the assignment is reallocated in an incremental fashion in linear time (assuming traversal choices are limited in number). The algorithm is studied systematically in simulation and also validated with physical robots.

A fundamental challenge in multi-robot systems is that global information is needed to succeed in some tasks, while the system's computation and sensing are fundamentally distributed. This paper considers the problem of estimating the relative density of robots in particular regions of the environment, but without wishing to incur the cost of obtaining a consistent metric representation. We compute a probability density function that describes positions of the robots within the system by leveraging properties of the underlying communication network. We introduce three different strategies for using and combining local measurements via a modified Parzen window kernel density method. The result is a representation that is most accurate near to the querying robot but which maintains qualitative properties of the global density. We argue that this a useful relaxation of the problem because it is meaningful from the perspective of the robots within the system itself. Validation takes the form of simulations with hundreds of simple robots.

Many envisioned applications of multi-robot swarms involve the detection, production or maintenance of global structures through only local means. This paper introduces a scalable, distributed algorithm to approximately characterize important global geometric and topological properties. For a given spatial arrangement of robots, the algorithm estimates the longest network (geodesic) distance in any direction as well as the average Euclidean distance only using locally sensed information. In so doing, the robots need only to communicate with and sense (range and bearing) nearby robots. The algorithm uses a greedy method to approximate both distance metrics via parallel one-way message traversals. We provide a bound for the number of such traversals, showing a global characterization is produced in a running time that is sublinear in the total number of robots. Along with this analysis, we conduct simulations with hundreds of robots to validate the algorithm.

BACKGROUND: HDX mass spectrometry is a powerful platform to probe protein structure dynamics during ligand binding, protein folding, enzyme catalysis, and such. HDX mass spectrometry analysis derives the protein structure dynamics based on the mass increase of a protein of which the backbone protons exchanged with solvent deuterium. Coupled with enzyme digestion and MS/MS analysis, HDX mass spectrometry can be used to study the regional dynamics of protein based on the m/z value or percentage of deuterium incorporation for the digested peptides in the HDX experiments. Various software packages have been developed to analyze HDX mass spectrometry data. Despite the progresses, proper and explicit statistical treatment is still lacking in most of the current HDX mass spectrometry software. In order to address this issue, we have developed the HDXanalyzer for the statistical analysis of HDX mass spectrometry data using R, Python, and RPY2. IMPLEMENTATION AND RESULTS: HDXanalyzer package contains three major modules, the data processing module, the statistical analysis module, and the user interface. RPY2 is employed to enable the connection of these three components, where the data processing module is implemented using Python and the statistical analysis module is implemented with R. RPY2 creates a low-level interface for R and allows the effective integration of statistical module for data processing. The data processing module generates the centroid for the peptides in form of m/z value, and the differences of centroids between the peptides derived from apo and ligand-bound protein allow us to evaluate whether the regions have significant changes in structure dynamics or not. Another option of the software is to calculate the deuterium incorporation rate for the comparison. The two types of statistical analyses are Paired Student's t-test and the linear combination of the intercept for multiple regression and ANCOVA model. The user interface is implemented with wxpython to facilitate the data visualization in graphs and the statistical analysis output presentation. In order to evaluate the software, a previously published xylanase HDX mass spectrometry analysis dataset is processed and presented. The results from the different statistical analysis methods are compared and shown to be similar. The statistical analysis results are overlaid with the three dimensional structure of the protein to highlight the regional structure dynamics changes in the xylanase enzyme. CONCLUSION: Statistical analysis provides crucial evaluation of whether a protein region is significantly protected or unprotected during the HDX mass spectrometry studies. Although there are several other available software programs to process HDX experimental data, HDXanalyzer is the first software program to offer multiple statistical methods to evaluate the changes in protein structure dynamics based on HDX mass spectrometry analysis. Moreover, the statistical analysis can be carried out for both m/z value and deuterium incorporation rate. In addition, the software package can be used for the data generated from a wide range of mass spectrometry instruments.

BACKGROUND: Enzyme dynamics has recently been shown to be crucial for structure-function relationship. Among various structure dynamics analysis platforms, HDX (hydrogen deuterium exchange) mass spectrometry stands out as an efficient and high-throughput way to analyze protein dynamics upon ligand binding. Despite the potential, limited research has employed the HDX mass spec platform to probe regional structure dynamics of enzymes. In particular, the technique has never been used for analyzing cell wall degrading enzymes. We hereby used xylanase as a model to explore the potential of HDX mass spectrometry for studying cell wall degrading enzymes. RESULTS: HDX mass spectrometry revealed significant intrinsic dynamics for the xylanase enzyme. Different regions of the enzymes are differentially stabilized in the apo enzyme. The comparison of substrate-binding enzymes revealed that xylohexaose can significantly stabilize the enzyme. Several regions including those near the reaction centres were significantly stabilized during the xylohexaose binding. As compared to xylohexaose, xylan induced relatively less protection in the enzyme, which may be due to the insolubility of the substrate. The structure relevance of the enzyme dynamics was discussed with reference to the three dimensional structure of the enzyme. HDX mass spectrometry revealed strong dynamics-function relevance and such relevance can be explored for the future enzyme improvement. CONCLUSION: Ligand-binding can lead to the significant stabilization at both regional and global level for enzymes like xylanase. HDX mass spectrometry is a powerful high-throughput platform to identify the key regions protected during the ligand binding and to explore the molecular mechanisms of the enzyme function. The HDX mass spectrometry analysis of cell wall degrading enzymes has provided a novel platform to guide the rational design of enzymes.