Models, code, and papers for "Dinesh Manocha":
We present an algorithm for realtime anomaly detection in low to medium density crowd videos using trajectory-level behavior learning. Our formulation combines online tracking algorithms from computer vision, non-linear pedestrian motion models from crowd simulation, and Bayesian learning techniques to automatically compute the trajectory-level pedestrian behaviors for each agent in the video. These learned behaviors are used to segment the trajectories and motions of different pedestrians or agents and detect anomalies. We demonstrate the interactive performance on the PETS ARENA dataset as well as indoor and outdoor crowd video benchmarks consisting of tens of human agents. We also discuss the implications of recent public policy and law enforcement issues relating to surveillance and our research.
We present a new time integrator for articulated body dynamics. We formulate the governing equations of the dynamics using only the position variables and recast the position-based articulated dynamics as an optimization problem. Our reformulation allows us to integrate the dynamics in a fully implicit manner without computing high-order derivatives. Therefore, under arbitrarily large timestep sizes, the stability of our time integration scheme is guaranteed using an off-the-shelf numerical optimizer. In addition to stability, we show that, similar to the Runge-Kutta method, the accuracy of our time integrator can also be increased arbitrarily by using a high-order collocation method. We provide efficient algorithms to perform time integration using our position-based formulation. We show that each iteration of optimization has a complexity of O(N) using Quasi-Newton method or O(N^2) using Newton's method, where N is the number of links. Finally, our method is highly parallelizable and can be accelerated using a Graphics Processing Unit (GPU). We highlight the efficiency and stability of our method on different benchmarks and compare the performance with prior articulated body dynamics simulation methods based on the Newton-Euler's equation. Our method is stable under a timestep size as large as 0.1s. Using a larger timestep size and less timesteps, our method achieves up to 4 times speedup on a single-core CPU. With GPU acceleration, we observe an additional 3-6 times speedup over a 4-core CPU.
We present a novel motion planning algorithm for transferring a liquid body from a source to a target container. Our approach uses a receding-horizon optimization strategy that takes into account fluid constraints and avoids collisions. In order to efficiently handle the high-dimensional configuration space of a liquid body, we use system identification to learn its dynamics characteristics using a neural network. We generate the training dataset using stochastic optimization in a transfer-problem-specific search space. The runtime feedback motion planner is used for real-time planning and we observe high success rate in our simulated 2D and 3D fluid transfer benchmarks.
We present an optimization-based motion planning algorithm to compute a smooth, collision-free trajectory for a manipulator used to transfer a liquid from a source to a target container. We take into account fluid dynamics constraints as part of trajectory computation. In order to avoid the high complexity of exact fluid simulation, we introduce a simplified dynamics model based on physically inspired approximations and system identification. Our optimization approach can incorporate various other constraints such as collision avoidance with the obstacles, kinematic and dynamics constraints of the manipulator, and fluid dynamics characteristics. We demonstrate the performance of our planner on different benchmarks corresponding to various obstacles and container shapes. Furthermore, we also evaluate its accuracy by validating the motion plan using an accurate but computationally costly Navier-Stokes fluid simulation.
We present a novel, realtime algorithm to compute the trajectory of each pedestrian in moderately dense crowd scenes. Our formulation is based on an adaptive particle filtering scheme that uses a multi-agent motion model based on velocity-obstacles, and takes into account local interactions as well as physical and personal constraints of each pedestrian. Our method dynamically changes the number of particles allocated to each pedestrian based on different confidence metrics. Additionally, we use a new high-definition crowd video dataset, which is used to evaluate the performance of different pedestrian tracking algorithms. This dataset consists of videos of indoor and outdoor scenes, recorded at different locations with 30-80 pedestrians. We highlight the performance benefits of our algorithm over prior techniques using this dataset. In practice, our algorithm can compute trajectories of tens of pedestrians on a multi-core desktop CPU at interactive rates (27-30 frames per second). To the best of our knowledge, our approach is 4-5 times faster than prior methods, which provide similar accuracy.
We present a novel, decentralized collision avoidance algorithm for navigating a swarm of quadrotors in dense environments populated with static and dynamic obstacles. Our algorithm relies on the concept of Optimal Reciprocal CollisionAvoidance (ORCA) and utilizes a flatness-based Model Predictive Control (MPC) to generate local collision-free trajectories for each quadrotor. We feedforward linearize the non-linear dynamics of the quadrotor and subsequently use this linearized model in our MPC framework. Our method is downwash conscious and computes safe trajectories that avoid quadrotors from entering each other's downwash regions during close proximity maneuvers. In addition, we account for the uncertainty in sensed position and velocity data using Kalman filtering. We evaluate the performance of our algorithm with other state-of-the-art methods and demonstrate its superior performance in terms of smoothness of generated trajectories and lower probability of collision during high velocity maneuvers.
We present an efficient algorithm to compute tight upper bounds of collision probability between two objects with positional uncertainties, whose error distributions are represented with non-Gaussian forms. Our approach can handle noisy datasets from depth sensors, whose distributions may correspond to Truncated Gaussian, Weighted Samples, or Truncated Gaussian Mixture Model. We derive tight probability bounds for convex shapes and extend them to non-convex shapes using hierarchical representations. We highlight the benefits of our approach over prior probabilistic collision detection algorithms in terms of tighter bounds (10x) and improved running time (3x). Moreover, we use our tight bounds to design an efficient and accurate motion planning algorithm for a 7-DOF robot arm operating in tight scenarios with sensor and motion uncertainties.
We present a novel approach for collision-free global navigation for continuous-time multi-agent systems with general linear dynamics. Our approach is general and can be used to perform collision-free navigation in 2D and 3D workspaces with narrow passages and crowded regions. As part of pre-computation, we compute multiple bridges in the narrow or tight regions in the workspace using kinodynamic RRT algorithms. Our bridge has certain geometric characteristics, that en- able us to calculate a collision-free trajectory for each agent using simple interpolation at runtime. Moreover, we combine interpolated bridge trajectories with local multi-agent navigation algorithms to compute global collision-free paths for each agent. The overall approach combines the performance benefits of coupled multi-agent algorithms with the pre- computed trajectories of the bridges to handle challenging scenarios. In practice, our approach can handle tens to hundreds of agents in real-time on a single CPU core in 2D and 3D workspaces.
We present a novel approach for generating plausible verbal interactions between virtual human-like agents and user avatars in shared virtual environments. Sense-Plan-Ask, or SPA, extends prior work in propositional planning and natural language processing to enable agents to plan with uncertain information, and leverage question and answer dialogue with other agents and avatars to obtain the needed information and complete their goals. The agents are additionally able to respond to questions from the avatars and other agents using natural-language enabling real-time multi-agent multi-avatar communication environments. Our algorithm can simulate tens of virtual agents at interactive rates interacting, moving, communicating, planning, and replanning. We find that our algorithm creates a small runtime cost and enables agents to complete their goals more effectively than agents without the ability to leverage natural-language communication. We demonstrate quantitative results on a set of simulated benchmarks and detail the results of a preliminary user-study conducted to evaluate the plausibility of the virtual interactions generated by SPA. Overall, we find that participants prefer SPA to prior techniques in 84\% of responses including significant benefits in terms of the plausibility of natural-language interactions and the positive impact of those interactions.
We present stress-minimizing (SM) metric, a new metric of grasp qualities. Unlike previous metrics that ignore the material of target objects, we assume that target objects are made of homogeneous isotopic materials. SM metric measures the maximal resistible external wrenches without causing fracture in the target objects. Therefore, SM metric is useful for robot grasping valuable and fragile objects. In this paper, we analyze the properties of this new metric, propose grasp planning algorithms to generate globally optimal grasps maximizing the SM metric, and compare the performance of the SM metric and a conventional metric. Our experiments show that SM metric is aware of the geometries of target objects while the conventional metric are not. We also show that the computational cost of the SM metric is on par with that of the conventional metric.
We present a novel algorithm for computing collision-free navigation for heterogeneous road-agents such as cars, tricycles, bicycles, and pedestrians in dense traffic. Our approach currently assumes the positions, shapes, and velocities of all vehicles and pedestrians are known and computes smooth trajectories for each agent by taking into account the dynamic constraints. We describe an efficient optimization-based algorithm for each road-agent based on reciprocal velocity obstacles that takes into account kinematic and dynamic constraints. Our algorithm uses tight fitting shape representations based on medial axis to compute collision-free trajectories in dense traffic situations. We evaluate the performance of our algorithm in real-world dense traffic scenarios and highlight the benefits over prior reciprocal collision avoidance schemes.
We present an efficient algorithm for motion planning and control of a robot system with a high number of degrees-of-freedom. These include high-DOF soft robots or an articulated robot interacting with a deformable environment. Our approach takes into account dynamics constraints and present a novel technique to accelerate the forward dynamic computation using a data-driven method. We precompute the forward dynamic function of the robot system on a hierarchical adaptive grid. Furthermore, we exploit the properties of underactuated robot systems and perform these computations for a few DOFs. We provide error bounds for our approximate forward dynamics computation and use our approach for optimization-based motion planning and reinforcement-learning-based feedback control. Our formulation is used for motion planning of two high DOF robot systems: a high-DOF line-actuated elastic robot arm and an underwater swimming robot operating in water. As compared to prior techniques based on exact dynamic function computation, we observe one to two orders of magnitude improvement in performance.
We present a novel algorithm for reciprocal collision avoidance between heterogeneous agents of different shapes and sizes. We present a novel CTMAT representation based on medial axis transform to compute a tight fitting bounding shape for each agent. Each CTMAT is represented using tuples, which are composed of circular arcs and line segments. Based on the reciprocal velocity obstacle formulation, we reduce the problem to solving a low-dimensional linear programming between each pair of tuples belonging to adjacent agents. We precompute the Minkowski Sums of tuples to accelerate the runtime performance. Finally, we provide an efficient method to update the orientation of each agent in a local manner. We have implemented the algorithm and highlight its performance on benchmarks corresponding to road traffic scenarios and different vehicles. The overall runtime performance is comparable to prior multi-agent collision avoidance algorithms that use circular or elliptical agents. Our approach is less conservative and results in fewer false collisions.
We present a motion planning algorithm to compute collision-free and smooth trajectories for high-DOF robots interacting with humans in a shared workspace. Our approach uses offline learning of human actions along with temporal coherence to predict the human actions. Our intention-aware online planning algorithm uses the learned database to compute a reliable trajectory based on the predicted actions. We represent the predicted human motion using a Gaussian distribution and compute tight upper bounds on collision probabilities for safe motion planning. We also describe novel techniques to account for noise in human motion prediction. We highlight the performance of our planning algorithm in complex simulated scenarios and real world benchmarks with 7-DOF robot arms operating in a workspace with a human performing complex tasks. We demonstrate the benefits of our intention-aware planner in terms of computing safe trajectories in such uncertain environments.
We present new algorithms to perform fast probabilistic collision queries between convex as well as non-convex objects. Our approach is applicable to general shapes, where one or more objects are represented using Gaussian probability distributions. We present a fast new algorithm for a pair of convex objects, and extend the approach to non-convex models using hierarchical representations. We highlight the performance of our algorithms with various convex and non-convex shapes on complex synthetic benchmarks and trajectory planning benchmarks for a 7-DOF Fetch robot arm.
We present a novel approach to perform probabilistic collision detection between a high-DOF robot and high-DOF obstacles in dynamic, uncertain environments. In dynamic environments with a high-DOF robot and moving obstacles, our approach efficiently computes accurate collision probability between the robot and obstacles with upper error bounds. Furthermore, we describe a prediction algorithm for future obstacle position and motion that accounts for both spatial and temporal uncertainties. We present a trajectory optimization algorithm for high-DOF robots in dynamic, uncertain environments based on probabilistic collision detection. We highlight motion planning performance in challenging scenarios with robot arms operating in environments with dynamically moving human obstacles.
We present a novel algorithm for collision-free kinematics of multiple manipulators in a shared workspace with moving obstacles. Our optimization-based approach simultaneously handles collision-free constraints based on reciprocal velocity obstacles and inverse kinematics constraints for high-DOF manipulators. We present an efficient method based on particle swarm optimization that can generate collision-free configurations for each redundant manipulator. Furthermore, our approach can be used to compute safe and oscillation-free trajectories in a few milli-seconds. We highlight the real-time performance of our algorithm on multiple Baxter robots with 14-DOF manipulators operating in a workspace with dynamic obstacles. Videos are available at https://sites.google.com/view/collision-free-kinematics
The complex physical properties of highly deformable materials such as clothes pose significant challenges fanipulation systems. We present a novel visual feedback dictionary-based method for manipulating defoor autonomous robotic mrmable objects towards a desired configuration. Our approach is based on visual servoing and we use an efficient technique to extract key features from the RGB sensor stream in the form of a histogram of deformable model features. These histogram features serve as high-level representations of the state of the deformable material. Next, we collect manipulation data and use a visual feedback dictionary that maps the velocity in the high-dimensional feature space to the velocity of the robotic end-effectors for manipulation. We have evaluated our approach on a set of complex manipulation tasks and human-robot manipulation tasks on different cloth pieces with varying material characteristics.
We present a novel method to compute the approximate global penetration depth (PD) between two non-convex geometric models. Our approach consists of two phases: offline precomputation and run-time queries. In the first phase, our formulation uses a novel sampling algorithm to precompute an approximation of the high-dimensional contact space between the pair of models. As compared with prior random sampling algorithms for contact space approximation, our propagation sampling considerably speeds up the precomputation and yields a high quality approximation. At run-time, we perform a nearest-neighbor query and local projection to efficiently compute the translational or generalized PD. We demonstrate the performance of our approach on complex 3D benchmarks with tens or hundreds of thousands of triangles, and we observe significant improvement over previous methods in terms of accuracy, with a modest improvement in the run-time performance.
We present a novel algorithm (DeepMNavigate) for global multi-agent navigation in dense scenarios using deep reinforcement learning. Our approach uses local and global information for each robot based on motion information maps. We use a three-layer CNN that uses these maps as input and generate a suitable action to drive each robot to its goal position. Our approach is general, learns an optimal policy using a multi-scenario, multi-state training algorithm, and can directly handle raw sensor measurements for local observations. We demonstrate the performance on complex, dense benchmarks with narrow passages on environments with tens of agents. We highlight the algorithm's benefits over prior learning methods and geometric decentralized algorithms in complex scenarios.