Review of multi-agent algorithms for collective behavior: a structural taxonomy
UNKNOWN
Pavone, Marco↗
Engineering topics
Bandyopadhyay, Saptarshi
Publications and source records attributed to Bandyopadhyay, Saptarshi.
Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy
In this paper, we review multi-agent collective behavior algorithms in the literature and classify them according to their underlying mathematical structure. For each mathematical technique, we identify the multi-agent coordination tasks it can be applied to, and we analyze its scalability, bandwidth use, and demonstrated maturity. We highlight how versatile techniques such as artificial potential functions can be used for applications ranging from low-level position control to high-level coordination and task allocation, we discuss possible reasons for the slow adoption of complex distributed coordination algorithms in the field, and we highlight areas for further research and development.
Pavone, Marco↗
Dynamic Shared Computing Resources for Multi-Robot Mars Exploration
The NASA roadmap for 2020 and beyond includes several key technologies which will have a game-changing impact on planetary exploration. The first of these is High Performance Spaceflight Computing (HPSC), which will provide orders of magnitude increases in processing power for next-generation rovers and orbiters (Doyle et al. 2013). The second is Delay Tolerant Networking, which overlays the Deep Space Network, providing internet-like abstractions and store-forward to route data through intermittent delays in connectivity. The third is a trend toward small, co-dependent robots included in flagship missions (MarCO, PUFFER, and Mars Heli). Taken together, these imply an increasing amount of communication and computing heterogeneity on Mars in coming decades. Motivated by these technological trends, we study the concept of Mars on-site shared analysis, information, and communication (MOSAIC) for Mars exploration. The key algorithmic problem associated with MOSAIC networks is simultaneous scheduling of computation, communication, and caching of data, which we illustrate using the three scenarios. We present models, preliminary solutions, and simulation results for two scenarios, showing how mission efficiency relates to communication bandwidth, processing power, geography of the environment, and optimal scheduling of computation, communication, and data caching. The third scenario illustrates future directions of this work.
Chien, Steve↗
Conceptual Ideas for Radio Telescope on the Far Side of the Moon
A radio telescope on the far-side of the Moon has tremendous advantages compared to Earth-based telescopes because it could observe the universe at wavelengths that are hitherto poorly explored by humans so far and the Moon acts as a physical shield that isolates the telescope from the radio interference and noises from Earth. This paper presents a novel concept for building a radio telescope on the far-side of the Moon. The main idea is to shape a suitable existing lunar crater (1 − 50km in diameter) on the far-side of the Moon into a spherical reflecting dish. The proposed Lunar Crater Radio Telescope (LCRT) would be able to observe the universe in the 5 − 100m wavelength band (i.e., 3 − 60MHz radio frequency band). The key innovations of this concept are: (1) LCRT would be the largest filled-aperture radio telescope in the Solar System. (2) LCRT could potentially make tremendous scientific discoveries in fields of cosmology and extrasolar planets by observing the universe in the 5−100m λ band(i.e., 3−60MHz ν band) that has been hitherto poorly explored. (3) It would require only a few robots from Earth and autonomously modify an existing lunar crater to build the LCRT; thereby significantly reducing launch weight and cost compared to all previous lunar surface telescope mission concepts. (4) Furthermore, the Earth based robots are not consumed during construction of LCRT. Therefore, they could create a network of LCRTs to (i) observe different regions of the universe, and (ii) enable lunar Very-Long-Baseline Interferometry (VLBI) astronomy. We envisage that this concept would unlock the potential for groundbreaking scientific discoveries in radio astronomy.
Rahmani, Amir↗
Distributed Spatiotemporal Motion Planning for Spacecraft Swarms in Cluttered Environments
This paper focuses on trajectory planning for spacecraft swarms in cluttered environments, like debris fields or the asteroid belt. Our objective is to reconfigure the spacecraft swarm to a desired formation in a distributed manner while minimizing fuel and avoiding collisions among themselves and with obstacles. In our prior work we proposed a novel distributed guidance algorithm for spacecraft swarms in static environments. In this paper, we present the Multi-Agent Moving-Obstacles Spherical Expansion and Sequential Convex Programming (MAMO SE-SCP) algorithm that extends our prior work to include spatiotemporal constraints such as time-varying, moving obstacles and desired time-varying terminal positions. In the MAMO SE-SCP algorithm, each agent uses a spherical-expansion-based sampling algorithm to cooperatively explore the time-varying environment, a distributed assignment algorithm to agree on the terminal position for each agent, and a sequential-convex-programming-based optimization step to compute the locally-optimal trajectories from the current location to the assigned time-varying terminal position while avoiding collision with other agents and moving obstacles. Simulation results demonstrate that the proposed distributed algorithm can be used by a spacecraft swarm to achieve a time-varying, desired formation around an object of interest in a dynamic environment with many moving and tumbling obstacles.
Bandyopadhyay, Saptarshi↗
Distributed Spatiotemporal Motion Planning for Spacecraft Swarms in Cluttered Environments
This paper focuses on trajectory planning for spacecraft swarms in cluttered environments, like debris fields or the asteroid belt. Our objective is to reconfigure the spacecraft swarm to a desired formation in a distributed manner while minimizing fuel and avoiding collisions among themselves and with the obstacles. In our prior work we proposed a novel distributed guidance algorithm for spacecraft swarms in static environments.1 In this paper, we present the Multi-Agent Moving-Obstacles Spherical Expansion and Sequential Convex Programming (MAMO SE–SCP) algorithm that extends our prior work to include spatiotemporal constraints such as time-varying, moving obstacles and desired time-varying terminal positions. In the MAMO SE–SCP algorithm, each agent uses a spherical-expansion-based sampling algorithm to cooperatively explore the time-varying environment, a distributed assignment algorithm to agree on the terminal position for each agent, and a sequential-convex-programming-based optimization step to compute the locally-optimal trajectories from the current location to the assigned time-varying terminal position while avoiding collision with other agent and the moving obstacles. Simulations results demonstrate that the proposed distributed algorithm can be used by a spacecraft swarm to achieve a time-varying, desired formation around an object of interest in a dynamic environment with many moving and tumbling obstacles.
Hadaegh, Fred Y.↗
Computationally Efficient Motion Planning Algorithms for Agile Autonomous Vehicles in Cluttered Environments
Fast, real-time motion planning of an agile, autonomous vehicle in a cluttered environment, with many geometrically-fixed obstacles, is a very complex problem, especially because of the vehicle dynamics constraints and resource constrained computational capabilities onboard the vehicle. In this paper, we present computationally-efficient versions of our novel motion planning algorithm called the Spherical Expansion and Sequential Convex Programming (SE–SCP) algorithm. The SE–SCP algorithm first uses a spherical-expansion-based randomized sampling algorithm to explore the workspace. Oncea path is found from the start position to the goal position, the algorithm computes a locally optimal trajectory, within its homotopy class for a desired cost function, by solving a sequence of convex optimization problems. Thus, the SE–SCP algorithm is anytime locally optimal and the trajectory is globally optimal if the number of samples tends to infinity. In this paper, we further enhance the computational efficiency of the SE–SCP algorithm using uni-directional and bi-directional rewiring techniques. We also present a detailed proof of the local optimality characteristics of the new SE–SCP algorithms for aspecial case of vehicle dynamics. Simulation examples involving quadrotor and spacecraft help demonstrate the effectiveness of our new algorithms.
Bandyopadhyay, Saptarshi↗
Autonomous Guidance Navigation and Control for Agile Quadrotors Using Polynomial Trajectory Planning and L1 Adaptive Control
We address the challenge to allow efficient autonomous flight in real world environments, both indoor and outdoor. We use a straight-line SE-SCP (Spherical Expansion and Sequential Convex Programming) [algorithm] to find an initial route through the environment and minimum snap trajectory generation using piecewise polynomials. Then, we implement an adaptive robust control able to address some robustness issues for quadrotors in outdoor flight, such as mass variation and wind disturbances. Coupling these techniques we allow high-speed and aggressive autonomous flight through obstacle-dense indoor environments, as well as address outdoor disturbances.
Landolfi, Mattia↗
Optimal Transport Based Control of Granular Imaging System in Space
"Orbiting Rainbows” is a paradigm for creating a space-based observatory (telescope) from confined and aligned granular media. The overall objective is to construct a very large and lightweight aperture in space using a cloud of micron-sized particles held in position and aligned by the application of external electromagnetic fields, thus alleviating the extreme expense of deploying and stabilizing large monolithic telescopes by reducing the mass of the primary aperture. Adaptive optics techniques for wavefront stabilization and computational imaging techniques are then used to remove the optical noise from the scattering reflections of the granular medium, and finally producing clean images within the diffraction limit. In this paper, we address one of the key challenges of this new paradigm, namely controlling the position and orientation of the granules or particles so that the cloud of particles achieves the desired shape of an ultra-lightweight telescope and points into the right orientation. A further complication arises due to the fact that the particles do not have any onboard actuators. A number of external electric-field-based actuators are used to control all the particles simultaneously. Moreover, the number of actuators are orders-of-magnitude smaller than the number of particles, making this system largely under-actuated. Since the cloud of particles in any plausible configuration can be modeled as a probability distribution over the workspace, we formulate this control challenge as an optimal transport problem and then show that our optimal transport based control law drives the cloud of particles from any initial distribution to the desired position distribution (optical surface) and angular distribution (polarization state). Simulation results demonstrate the effectiveness of our approach.
Bandyopadhyay, Saptarshi↗
Distributed Fast Motion Planning for Spacecraft Swarms in Cluttered Environments using Spherical Expansions and Sequence of Convex Optimization Problems
This paper presents a novel guidance algorithm for spacecraft swarms in an environment cluttered with many obstacles like a debris field or the asteroid belt. The objective of this algorithm is to reconfigure the swarm to a desired formation in a distributed manner while minimizing fuel and avoiding collisions among themselves and with the obstacles. The agents first use a spherical-expansion-based sampling algorithm to cooperatively explore the workspace and find paths to the desired terminal positions. Using a distributed assignment algorithm, the agents converge on an optimal assignment of the target locations in the desired formation. Then each agent generates a locally optimal trajectory from its current location to its terminal position by solving a sequence of convex optimization problems. As the agent moves along this trajectory, it receives the position of other agents and updates its trajectory to avoid collisions with other agents and the obstacles. Thus the swarm achieves the desired formation in a distributed manner while avoiding collisions. Moreover, this algorithm is computationally efficient, therefore it can be implemented onboard resource-constrained spacecraft. Simulations results show that the proposed distributed algorithm can be used by a spacecraft swarm to reconfigure a desired formation around an asteroid in a collision-free manner.
Bandyopadhyay, Saptarshi↗
Distributed fast motion planning for spacecraft swarms in cluttered environments
UNKNOWN
Hadaegh, Fred Y.↗