Mixed-Integer Linear Programming Models for Multi-Robot Non-Adversarial Search

In this letter, we consider the Multi-Robot Efficient Search Path Planning (MESPP) problem, where a team of robots is deployed in a graph-represented environment to capture a moving target within a given deadline. We prove this problem to be NP-hard, and present the first set of Mixed-Integer Linear Programming (MILP) models to tackle the MESPP problem. Our models are the first to encompass multiple searchers, arbitrary capture ranges, and false negatives simultaneously. While state-of-the-art algorithms for MESPP are based on simple path enumeration, the adoption of MILP as a planning paradigm allows to leverage the powerful techniques of modern solvers, yielding better computational performance and, as a consequence, longer planning horizons. The models are designed for computing optimal solutions offline, but can be easily adapted for a distributed online approach. Our simulations show that it is possible to achieve 98% decrease in computational time relative to the previous state-of-the-art. We also show that the distributed approach performs nearly as well as the centralized, within 6% in the settings studied in this letter, with the advantage of requiring significant less time - an important consideration in practical search missions.

Planning Paths Through Unknown Space by Imagining What Lies Therein

This paper presents a novel framework for planning paths in maps containing unknown spaces, such as from occlusions. Our approach takes as input a semantically-annotated point cloud, and leverages an image inpainting neural network to generate a reasonable model of unknown space as free or occupied. Our validation campaign shows that it is possible to greatly increase the performance of standard pathfinding algorithms which adopt the general optimistic assumption of treating unknown space as free.

Interactive Natural Language-based Person Search

In this work, we consider the problem of searching people in an unconstrained environment, with natural language descriptions. Specifically, we study how to systematically design an algorithm to effectively acquire descriptions from humans. An algorithm is proposed by adapting models, used for visual and language understanding, to search a person of interest (POI) in a principled way, achieving promising results without the need to re-design another complicated model. We then investigate an iterative question-answering (QA) strategy that enable robots to request additional information about the POIs appearance from the user. To this end, we introduce a greedy algorithm to rank questions in terms of their significance, and equip the algorithm with the capability to dynamically adjust the length of human-robot interaction according to models uncertainty. Our approach is validated not only on benchmark datasets but on a mobile robot, moving in a dynamic and crowded environment.

Pedestrian Motion Model Using Non-Parametric Trajectory Clustering and Discrete Transition Points

This paper presents a pedestrian motion model that includes both low level trajectory patterns, and high level discrete transitions. The inclusion of both levels creates a more general predictive model, allowing for more meaningful prediction and reasoning about pedestrian trajectories, as compared to the current state of the art. The model uses an iterative clustering algorithm with (1) Dirichlet Process Gaussian Processes to cluster trajectories into continuous motion patterns and (2) hypothesis testing to identify discrete transitions in the data called transition points. The model iteratively splits full trajectories into sub-trajectory clusters based on transition points, where pedestrians make discrete decisions. State transition probabilities are then learned over the transition points and trajectory clusters. The model is for online prediction of motions, and detection of anomalous trajectories. The proposed model is validated on the Duke MTMC dataset to demonstrate identification of low level trajectory clusters and high level transitions, and the ability to predict pedestrian motion and detect anomalies online with high accuracy.

On Generalized Bayesian Data Fusion with Complex Models in Large Scale Networks

Recent advances in communications, mobile computing, and artificial intelligence have greatly expanded the application space of intelligent distributed sensor networks. This in turn motivates the development of generalized Bayesian decentralized data fusion (DDF) algorithms for robust and efficient information sharing among autonomous agents using probabilistic belief models. However, DDF is significantly challenging to implement for general real-world applications requiring the use of dynamic/ad hoc network topologies and complex belief models, such as Gaussian mixtures or hybrid Bayesian networks. To tackle these issues, we first discuss some new key mathematical insights about exact DDF and conservative approximations to DDF. These insights are then used to develop novel generalized DDF algorithms for complex beliefs based on mixture pdfs and conditional factors. Numerical examples motivated by multi-robot target search demonstrate that our methods lead to significantly better fusion results, and thus have great potential to enhance distributed intelligent reasoning in sensor networks.