This paper addresses a variant of the conflict-based search (CBS) algorithm for multi-agent path finding, presenting an effective cluster reasoning heuristic that searches for and detects conflicts involving more than two agents. The proposed in-depth cluster reasoning technique systematically alters the reference agent when computing the heuristic cost-to-go, and this yields a tighter estimate. It then balances the complexity of expanding CBS nodes against that of locating clusters by systematically scheduling the associated parameters. Numerical experiments demonstrate that the proposed algorithm successfully detects clusters that state-of-the-art algorithms cannot identify and produces solutions for various extreme scenarios that existing algorithms cannot solve.

In uncertain and dynamic environments, decentralized data fusion (DDF) techniques have been widely used to estimate the states and the uncertainty levels over large mission spaces in a robust and scalable way. In data fusion frameworks using distributed sensor networks, undetected sensor failures can degrade the quality of fusion results of the entire system. Therefore, DDF methods which are robust to inconsistent data are needed. In this paper, a fault-tolerant Bayesian DDF method using Gaussian mixture models is developed. The probability of agent reliability states, which represent consistency of local estimates that agents share with their neighbors, are modeled as weights of mixture models and estimated together with the target process. The target process and reliability states are updated in a decentralized Bayesian way, exploiting the properties of Gaussian mixture models. To prevent the hypothesis explosion problem of Gaussian mixture models, a mixture compression method considering the physical meaning of mixture weights is utilized. A numerical simulation on a 2D dynamic target tracking problem is presented to verify performance of the suggested algorithm and compared with existing DDF methods. It is shown that the suggested algorithm gives more compact fusion results compared to existing fault-tolerant DDF method.

Occupancy mapping has been widely utilized to represent the surroundings for autonomous robots to perform tasks such as navigation and manipulation. While occupancy mapping in 2-D environments has been well-studied, there have been few approaches suitable for 3-D dynamic occupancy mapping which is essential for aerial robots. This paper presents a novel 3-D dynamic occupancy mapping algorithm called DS-K3DOM. We first establish a Bayesian method to sequentially update occupancy maps for a stream of measurements based on the random finite set theory. Then, we approximate it with particles in the Dempster-Shafer domain to enable real-time computation. Moreover, the algorithm applies kernel-based inference with Dirichlet basic belief assignment to enable dense mapping from sparse measurements. The efficacy of the proposed algorithm is demonstrated through simulations and real experimentsiiThe code is available at: https://github.com/JuyeopHan/dsk3dom_public.

We present a hierarchical planning and control framework that enables an agent to perform various tasks and adapt to a new task flexibly. Rather than learning an individual policy for each particular task, the proposed framework, DISH, distills a hierarchical policy from a set of tasks by representation and reinforcement learning. The framework is based on the idea of latent variable models that represent high-dimensional observations using low-dimensional latent variables. The resulting policy consists of two levels of hierarchy: (i) a planning module that reasons a sequence of latent intentions that would lead to an optimistic future and (ii) a feedback control policy, shared across the tasks, that executes the inferred intention. Because the planning is performed in low-dimensional latent space, the learned policy can immediately be used to solve or adapt to new tasks without additional training. We demonstrate the proposed framework can learn compact representations (3- and 1-dimensional latent states and commands for a humanoid with 197- and 36-dimensional state features and actions) while solving a small number of imitation tasks, and the resulting policy is directly applicable to other types of tasks, i.e., navigation in cluttered environments.

This paper presents a navigation network based deep reinforcement learning framework for autonomous indoor robot exploration. The presented method features a pattern cognitive non-myopic exploration strategy that can better reflect universal preferences for structure. We propose the Extendable Navigation Network (ENN) to encode the partially observed high-dimensional indoor Euclidean space to a sparse graph representation. The robot’s motion is generated by a learned Q-network whose input is the ENN. The proposed framework is applied to a robot equipped with a 2D LIDAR sensor in the GAZEBO simulation where floor plans of real buildings are implemented. The experiments demonstrate the efficiency of the framework in terms of exploration time.

Mapping three-dimensional (3-D) dynamic environments is essential for aerial robots but challenging to consider the increased dimensions in both space and time compared to 2-D static mapping. This paper presents a kernel-based 3-D dynamic occupancy mapping algorithm, K3DOM, that distinguishes between static and dynamic objects while estimating the velocities of dynamic cells via particle tracking. The proposed algorithm brings the benefits of kernel inference such as its simple computation, consideration of spatial correlation, and natural measure of uncertainty to the domain of dynamic mapping. We formulate the dynamic occupancy mapping problem in a Bayesian framework and represent the map through Dirichlet distribution to update posteriors in a recursive way with intuitive heuristics. The proposed algorithm demonstrates its promising performance compared to baseline in diverse scenarios simulated in ROS environments.

We present a representation learning algorithm that learns a low-dimensional latent dynamical system from high-dimensional sequential raw data, e.g., video. The framework builds upon recent advances in amortized inference methods that use both an inference network and a refinement procedure to output samples from a variational distribution given an observation sequence, and takes advantage of the duality between control and inference to approximately solve the intractable inference problem using the path integral control approach. The learned dynamical model can be used to predict and plan the future states; we also present the efficient planning method that exploits the learned low-dimensional latent dynamics. Numerical experiments show that the proposed path-integral control based variational inference method leads to tighter lower bounds in statistical model learning of sequential data. Supplementary video: https://youtu.be/xCp35crUoLQ

This work presents a multiscale framework to solve a class of stochastic optimal control problems in the context of robot motion planning and control in a complex environment. In order to handle complications resulting from a large decision space and complex environmental geometry, two key concepts are adopted: (a) a diffusion wavelet representation of the Markov chain for hierarchical abstraction of the state space; and (b) a desirability function-based representation of the Markov decision process (MDP) to efficiently calculate the optimal policy. In the proposed framework, a global plan that compressively takes into account the long time/length-scale state transition is first obtained by approximately solving an MDP whose desirability function is represented by coarse scale bases in the hierarchical abstraction. Then, a detailed local plan is computed by solving an MDP that considers wavelet bases associated with a focused region of the state space, guided by the global plan. The resulting multiscale plan is utilized to finally compute a continuous-time optimal control policy within a receding horizon implementation. Two numerical examples are presented to demonstrate the applicability and validity of the proposed approach.

This work presents an efficient method to solve a class of continuous-time, continuous-space stochastic optimal control problems of robot motion in a cluttered environment. The method builds upon a path integral representation of the stochastic optimal control problem that allows computation of the optimal solution through sampling and estimation process. As this sampling process often leads to a local minimum especially when the state space is highly non-convex due to the obstacle field, we present an efficient method to alleviate this issue by devising a proposed topological motion planning algorithm. Combined with a receding-horizon scheme in execution of the optimal control solution, the proposed method can generate a dynamically feasible and collision-free trajectory while reducing concern about local optima. Illustrative numerical examples are presented to demonstrate the applicability and validity of the proposed approach.

This paper presents modified formulations of coupled-constraints consensus based bundle algorithm to resolve the cooperative transportation problem. Formulation frameworks for a cooperative transportation mission are suggested. Suggested frameworks are deal with various types of constraints and characteristics of cooperative transportation mission. In this paper, several modifications on reward function and arrival time calculation are suggested to handle the constraints of cooperative transportation mission.

In this paper, interception of border crossers along a border strip bounded by a border line and a military boundary line is considered. Performance measure of interception strategy of a guard is mission failure rate: pass rate of border crossers through the border strip. A defenceable area and a lateral defense length of sequential two-target interception are introduced to derive an expression of an upper bound of pass rate. Numerical simulations of border defense validate the upper bound.

This paper presents a cooperative distributed planning algorithm that ensures network connectivity for a team of heterogeneous agents operating in dynamic and communication-limited environments. The algorithm, named CBBA with Relays, builds on the Consensus-Based Bundle Algorithm (CBBA), a distributed task allocation framework developed previously by the authors and their colleagues. Information available through existing consensus phases of CBBA is leveraged to predict the network topology and to propose relay tasks to repair connectivity violations. The algorithm ensures network connectivity during task execution while preserving the distributed and polynomial-time guarantees of CBBA. By employing under-utilized agents as communication relays, CBBA with Relays improves the range of the team without limiting the scope of the active agents, thus improving mission performance. The algorithm is validated through simulation trials and through experimental indoor and outdoor field tests, demonstrating the real-time applicability of the approach.

This paper presents several analysis of mutual information that is often used to define the objective function for trajectory planning (and scheduling) of sensor networks, when the goal is to improve the forecast accuracy of some quantities of interest. The approach extends the present author's prior work in order to consider more general notion of verification entities and to enable more robust decision with potential uncertainty in the mission specifications. The expression of mutual information for windowed forecasting, in which the verification entities are defined by a finite time window instead of a single time instance, is derived and quantified without adding significant computational cost. It is also demonstrated that the sensitivity of mutual information to the variation of verification time can be calculated in the same process of computing the mutual information. Simple numerical examples are presented for preliminary validation of the applicability of the proposed analysis.

This paper addresses task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, i.e., the consensus-based bundle algorithm (CBBA). These algorithms utilize a market-based decision strategy as the mechanism for decentralized task selection and use a consensus routine based on local communication as the conflict resolution mechanism to achieve agreement on the winning bid values. Under reasonable assumptions on the scoring scheme, both of the proposed algorithms are proven to guarantee convergence to a conflict-free assignment, and it is shown that the converged solutions exhibit provable worst-case performance. It is also demonstrated that CBAA and CBBA produce conflict-free feasible solutions that are robust to both inconsistencies in the situational awareness across the fleet and variations in the communication network topology. Numerical experiments confirm superior convergence properties and performance when compared with existing auction-based task-allocation algorithms.

A controller to stabilize F-16 aircraft flying with a steady state around the altitude of 25,000 ft is considered. The nonlinear pitching motion model of F-16 is linearized in the range of the flight envelope of velocity vs. altitude. Then the statically unstable system is stabilized by applying feedback linearization. As the gain-scheduling method is introduced at various operating points within the flight envelope, the optimized controller is designed all over the envelope. Evolutionary Optimization based on Lagrangian (Evolian II) is used to optimize the controller gains P and I satisfying complex nonlinear constraints.

The three-dimensional target optimal evasion problem against a proportionally guided missile is considered. The optimal evasion problem is formulated as a constrained optimization problem whose payoff is the intercept time and constraint is the capture condition. The target's control variables and the final time are parameterized for an application of direct optimization methods. The co-evolutionary augmented Lagrangian method is implemented to solve the derived constrained parameter optimization problem. A scheduled smoothing technique is introduced to avoid the chattering effect. Numerical simulations for three-dimensional engagement scenarios are conducted, and the no-escape envelopes are obtained.