Vision-Language Models (VLMs) have shown great success as foundational models for downstream vision and natural language applications in a variety of domains. However, these models are limited to reasoning over objects and actions currently visible on the image plane. We present a spatial extension to the VLM, which leverages spatially-localized egocentric video demonstrations to augment VLMs in two ways - through understanding spatial task-affordances, i.e. where an agent must be for the task to physically take place, and the localization of that task relative to the egocentric viewer. We show our approach outperforms the baseline of using a VLM to map similarity of a task's description over a set of location-tagged images. Our approach has less error both on predicting where a task may take place and on predicting what tasks are likely to happen at the current location. The resulting representation will enable robots to use egocentric sensing to navigate to, or around, physical regions of interest for novel tasks specified in natural language.

Most path planning techniques use exact, global information of the environment to make optimal or near-optimal plans. In contrast, humans navigate using only local information, which they must augment with their understanding of typical building layouts to guess what lies ahead, while integrating what they have seen already to form mental representations of building structure. Here, we propose Scene Planning Networks (SPNets), a neural network based approach for formulating the long-range navigation problem as a series of local decisions similar to what humans face when navigating. Agents navigating using SPNets build additive neural representations of previous observations to understand local obstacle structure, and use a network-based planning approach to plan the next steps towards a fuzzy goal region. Our approach reproduces several important aspects of human behavior that are not captured by either full global planning or simple local heuristics.

With recent advances in hardware technology, autonomous robots are increasingly present in research activities outside of robotics, performing a multitude of tasks such as image capture and sample collection. However, user interfaces for task-oriented robots have not kept pace with hardware breakthroughs. Current planning and control interfaces for robots are not intuitive and often place a large cognitive burden on those who are not highly trained in their use. Augmented reality (AR) has also seen major advances in recent years. This demonstration illustrates an initial system design for an AR user interface for path planning with robotics.

Over the last two decades there has been a proliferation of methods for simulating crowds of humans. As the number of different methods and their complexity increases, it becomes increasingly unrealistic to expect researchers and users to keep up with all the possible options and trade-offs. We therefore see the need for tools that can facilitate both domain experts and non-expert users of crowd simulation in making high-level decisions about the best simulation methods to use in different scenarios. In this paper, we leverage trajectory data from human crowds and machine learning techniques to learn a manifold which captures representative local navigation scenarios that humans encounter in real life. We show the applicability of this manifold in crowd research, including analyzing trends in simulation accuracy, and creating automated systems to assist in choosing an appropriate simulation method for a given scenario.

Large multi-agent systems such as crowds involve inter-agent interactions that are typically anticipatory in nature, depending strongly on both the positions and the velocities of agents. We show how the nonlinear, anticipatory forces seen in multi-agent systems can be made compatible with recent work on energy-based formulations in physics-based animation, and propose a simple and effective optimization-based integration scheme for implicit integration of such systems. We apply this approach to crowd simulation by using a state-of-the-art model derived from a recent analysis of human crowd data, and adapting it to our framework. Our approach provides, for the first time, guaranteed collision-free motion while simultaneously maintaining high-quality collective behavior in a way that is insensitive to simulation parameters such as time step size and crowd density. These benefits are demonstrated through simulation results on various challenging scenarios and validation against real-world crowd data.

In crowded multi-agent navigation environments, the motion of the agents is significantly constrained by the motion of the nearby agents. This makes planning paths very difficult and leads to inefficient global motion. To address this problem, we propose a new distributed approach to coordinate the motions of agents in crowded environments. With our approach, agents take into account the velocities and goals of their neighbors and optimize their motion accordingly and in real-time. We experimentally validate our coordination approach in a variety of scenarios and show that its performance scales to scenarios with hundreds of agents.

In this paper, we introduce an optimization-based approach for creating a simulation-driven game designed to teach players about nano-technology. We focus our effort on Metal-Organic Frameworks (MOFs), a new class of nano-materials used for a wide variety of safety, filtering, and manufacturing tasks. In particular, we design a tool to allow users to create their own unique MOFs, introduce a new form of interactive simulation of MOF structures, and validate our new simulation model with existing offline chemical simulation techniques. We combine our new design tool and simulation technique into a simple game called Master of Filtering, designed to let players design and test brand new MOFs within an interactive game setting. Following an optimization-driven approach, we are able to generate an initiative scoring mechanism such as higher scores in the game are positively correlated with better key chemical properties of the user-designed MOFs.

Animated digital characters play an important role in virtual experiences. In this work, we utilize data from a large scale user study as training data for a generative model for producing a variety of animated smiles. Our method involves a four stage process that samples a variety of facial expressions, and annotates them with perceived happiness from the user study. The expressions are then transformed into a standardized space and used by a non-parametric classifier to predict happiness of new smiles.

We introduce the problem of navigating a group of robots having prioritized formations amidst static and dynamic obstacles. Our formulation allows users to define a number of template formations, each with a specified priority value. At each planning cycle, we compute a new formation which accounts for both these priority values and the safe progress of the robots towards their goal. To this end, we introduce a new velocity-based navigation approach which we denote as Formation Velocity Obstacles (FVO). Like other velocity-based approaches, FVO allows anticipatory collision avoidance accounting for the likely future motion of nearby obstacles. However, we extend these previous approaches and allow anisotropic agents which rotate themselves to orient along their direction of travel. We integrate these FVOs with a Bayesian framework to infer priority values for arbitrary formations from the user-given templates. The result is a complete framework for prioritized formation planning.

An autonomous robot team can be employed for continuous and strategic coverage of arbitrary environments for different missions. In this work, we propose an anytime approach for creating multi-robot patrolling policies. Our approach involves a novel extension of Monte Carlo Tree Search (MCTS) to allow robots to have life-long, cyclic policies so as to provide continual coverage of an environment. Our proposed method can generate near-optimal policies for a team of robots for small environments in real-time (and in larger environments in under a minute). By incorporating additional planning heuristics we are able to plan coordinated patrolling paths for teams of several robots in large environments quickly on commodity hardware.

In multi-robot systems, efficiently navigating in a a partially-known environment is an ubiquitous but challenging task, as each robot must account for the uncertainty introduced, for example, by other moving robots. This uncertainty makes pre-computed plans not always applicable, and often hinders the desired efficient use of the robot's resources. In this work, we present a local anytime approach for robot motion planning that accounts for the uncertainty of the environment by generating `snapshots' of possible future scenarios. Our approach adapts the Hindsight optimization technique to allow robots to plan their immediate motion based on long-term efficiency. We validate our approach by comparing the efficiency on the paths executed against a state-of-the art navigation technique in a variety of scenarios, and show that by accounting for the uncertainty in the environment, agents can improve their time- and energy-efficient motions.

Abstract We present a novel approach for analyzing the quality of multi‐agent crowd simulation algorithms. Our approach is data‐driven, taking as input a set of user‐defined metrics and reference training data, either synthetic or from video footage of real crowds. Given a simulation, we formulate the crowd analysis problem as an anomaly detection problem and exploit state‐of‐the‐art outlier detection algorithms to address it. To that end, we introduce a new framework for the visual analysis of crowd simulations. Our framework allows us to capture potentially erroneous behaviors on a per‐agent basis either by automatically detecting outliers based on individual evaluation metrics or by accounting for multiple evaluation criteria in a principled fashion using Principle Component Analysis and the notion of Pareto Optimality. We discuss optimizations necessary to allow real‐time performance on large datasets and demonstrate the applicability of our framework through the analysis of simulations created by several widely‐used methods, including a simulation from a commercial game.

Abstract We present a novel framework to evaluate multi‐agent crowd simulation algorithms based on real‐world observations of crowd movements. A key aspect of our approach is to enable fair comparisons by automatically estimating the parameters that enable the simulation algorithms to best fit the given data. We formulate parameter estimation as an optimization problem, and propose a general framework to solve the combinatorial optimization problem for all parameterized crowd simulation algorithms. Our framework supports a variety of metrics to compare reference data and simulation outputs. The reference data may correspond to recorded trajectories, macroscopic parameters, or artist‐driven sketches. We demonstrate the benefits of our framework for example‐based simulation, modeling of cultural variations, artist‐driven crowd animation, and relative comparison of some widely‐used multi‐agent simulation algorithms.

Human crowds are becoming an increasingly important component of video games and virtual environments. However, as these virtual worlds become more realistic, the simulation of human crowds must become more sophisticated to keep pace. Much recent work in the field of crowd simulation has focused on improving aspects relating to navigation and collision avoidance in order to create complex, collision free trajectories. However, this paper argues that an equally important aspect of creating believable crowds is simulating aspects beyond navigation such as the internal psychological state of a simulated agent and external physical forces. We also discuss how recently proposed methods can be used to simulate these physical and psychological aspects of crowd simulations while maintaining high-quality, collision free motion.

We present an object-centric formulation for parallel rigid body simulation that supports variable length integration time steps through rollbacks. We combine our object-centric simulation framework with a novel spatiotemporal data structure to reduce global synchronization and achieve interactive, real-time simulations which scale across many CPU cores. Additionally, we provide proofs that both our proposed data structure and our object-centric formulation are deadlock-free. We implement our approach with the functional programming language Erlang, and test the performance and scalability of our method over several scenarios consisting of hundreds of interacting objects.

This paper presents LQG-Obstacles, a new concept that combines linear-quadratic feedback control of mobile robots with guaranteed avoidance of collisions with obstacles. Our approach generalizes the concept of Velocity Obstacles [3] to any robotic system with a linear Gaussian dynamics model. We integrate a Kalman filter for state estimation and an LQR feedback controller into a closed-loop dynamics model of which a higher-level control objective is the “control input”. We then define the LQG-Obstacle as the set of control objectives that result in a collision with high probability. Selecting a control objective outside the LQG-Obstacle then produces collision-free motion. We demonstrate the potential of LQG-Obstacles by safely and smoothly navigating a simulated quadrotor helicopter with complex non-linear dynamics and motion and sensing uncertainty through three-dimensional environments with obstacles and narrow passages.

We propose a new technique to simulate dynamic patterns of crowd behaviors using stress modeling. Our model accounts for permanent, stable disposition and the dynamic nature of human behaviors that change in response to the situation. The resulting approach accounts for changes in behavior in response to external stressors based on well-known theories in psychology. We combine this model with recent techniques on personality modeling for multi-agent simulations to capture a wide variety of behavioral changes and stressors. The overall formulation allows different stressors, expressed as functions of space and time, including time pressure, positional stressors, area stressors and inter-personal stressors. This model can be used to simulate dynamic crowd behaviors at interactive rates, including walking at variable speeds, breaking lane-formation over time, and cutting through a normal flow. We also perform qualitative and quantitative comparisons between our simulation results and real-world observations.

We present an information-theoretic method to measure the similarity between a given set of observed, real-world data and visual simulation technique for aggregate crowd motions of a complex system consisting of many individual agents. This metric uses a two-step process to quantify a simulator's ability to reproduce the collective behaviors of the whole system, as observed in the recorded real-world data. First, Bayesian inference is used to estimate the simulation states which best correspond to the observed data, then a maximum likelihood estimator is used to approximate the prediction errors. This process is iterated using the EM-algorithm to produce a robust, statistical estimate of the magnitude of the prediction error as measured by its entropy (smaller is better). This metric serves as a simulator-to-data similarity measurement. We evaluated the metric in terms of robustness to sensor noise, consistency across different datasets and simulation methods, and correlation to perceptual metrics.

We present an approach for collision avoidance for mobile robots that takes into account acceleration constraints. We discuss both the case of navigating a single robot among moving obstacles, and the case of multiple robots reciprocally avoiding collisions with each other while navigating a common workspace. Inspired by the concept of velocity obstacles [3], we introduce the acceleration-velocity obstacle (AVO) to let a robot avoid collisions with moving obstacles while obeying acceleration constraints. AVO characterizes the set of new velocities the robot can safely reach and adopt using proportional control of the acceleration. We extend this concept to reciprocal collision avoidance for multi-robot settings, by letting each robot take half of the responsibility of avoiding pairwise collisions. Our formulation guarantees collision-free navigation even as the robots act independently and simultaneously, without coordination. Our approach is designed for holonomic robots, but can also be applied to kinematically constrained non-holonomic robots such as cars. We have implemented our approach, and we show simulation results in challenging environments with large numbers of robots and obstacles.

We present the hybrid reciprocal velocity obstacle for collision-free and oscillation-free navigation of multiple mobile robots or virtual agents. Each robot senses its surroundings and acts independently without central coordination or communication with other robots. Our approach uses both the current position and the velocity of other robots to compute their future trajectories in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots sense their surroundings as well and change their trajectories accordingly. We apply hybrid reciprocal velocity obstacles to iRobot Create mobile robots and demonstrate direct, collision-free, and oscillation-free navigation.

We present an approach to reciprocal collision avoidance, where multiple mobile agents must avoid collisions with each other while moving in a common workspace. Each agent acts fully independently, and does not communicate with others. Yet our approach guarantees that all agents will be collision-free for at least a fixed amount of time. Our approach provides a sufficient condition for collision-free motion. Given the agent's objective, the optimal collision-free action can be computed very efficiently, as it is the solution to a two-dimensional linear program. We show our approach on dense and complex simulation scenarios involving thousands of agents at fast real-time running times.

We present a method for smooth and collision-free navigation for multiple independent robots under differential-drive constraints. Our algorithm is based on the optimal reciprocal collision avoidance formulation and guarantees both smoothness in the trajectories of the robots and locally collision-free paths. We provide proofs of these guarantees and demonstrate the effectiveness of our method in experimental scenarios using iRobot Create mobile robots navigating amongst each other.

We present an approach for smooth and collision-free navigation of multiple mobile robots amongst each other. Each robot senses its surroundings and acts independently without central coordination or communication with other robots. Our approach uses both the current position and the velocity of other robots to predict their future trajectory in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots also sense their surroundings and change their trajectories accordingly. We build on prior work related to velocity obstacles and reciprocal velocity obstacles and introduce the concept of hybrid reciprocal velocity obstacles for collision avoidance that takes into account the kinematics of the robots and uncertainty in sensor data. We apply our approach to a set of iRobot Create robots using centralized sensing and show natural, direct, and collision-free navigation in several challenging scenarios.

We present a novel algorithm for collision-free navigation of a large number of independent agents in complex and dynamic environments. We introduce adaptive roadmaps to perform global path planning for each agent simultaneously. Our algorithm takes into account dynamic obstacles and interagents interaction forces to continuously update the roadmap based on a physically-based dynamics simulator. In order to efficiently update the links, we perform adaptive particle-based sampling along the links. We also introduce the notion of 'link bands' to resolve collisions among multiple agents. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.

We present a novel algorithm for navigating a large number of independent agents in complex and dynamic environments. We compute adaptive roadmaps to perform global path planning for each agent simultaneously. We take into account dynamic obstacles and inter-agents interaction forces to continuously update the roadmap by using a physically-based agent dynamics simulator. We also introduce the notion of 'link bands' for resolving collisions among multiple agents. We present efficient techniques to compute the guiding path forces and perform lazy updates to the roadmap. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.