See the available Funding Support.
This work seeks to generate high-quality paths for complex dynamic systems. Some of the challenges addressed by this project include extending asymptotically near-optimal motion planning to systems with complex dynamics and learning better metrics for such systems. In general, providing asymptotically optimal motion planning solutions requires a boundary value problem (BVP) solver; however, this work aims to show that convergence to near-optimal solutions can be achieved without the BVP solver. This is especially important for physics-based simulations, where the system dynamics are unknown and BVP solvers for the system do not exist.
Rearranging multiple objects is a critical skill for robots so that they can effectively deal with clutter in human spaces. This is a challenging problem as it involves combinatorially large, continuous C-spaces involving multiple movable bodies and complex kinematic constraints. This work focuses on efficiently solving general rearrangement tasks, which may correspond to easier monotone challenges or to harder, non-monotone instances. Monotone problems corresponds to the case when objects need to be grasped only once so as to be rearranged. Non-monotone challenges are recognized as hard rearrangement instances given that the method has to detect intermediate placements for some objects in order to find a solution to such problems.
Tensegrity robots are a lightweight, modular, and resilient class of mobile platforms that have been proposed for rugged operations such as the exploration of other planets and moons. While the many actuated cables of these robots facilitate effective adaptation to highly unstructured environments, they also produce high dimensional and strongly coupled nonlinear system dynamics that are unintuitive and difficult to control. This project aims to provide new algorithmic, mathematical, and software tools that meet this challenge and provide dynamically feasible trajectories for purposeful long-term navigation of tensegrity robots in uneven terrain.
Recent results have shown that sampling-based motion planning techniques can converge to returning optimal paths for a variety of systems. These guarantees only hold asymptotically (i.e. after infinite computation time) and practically, these methods create dense structures. This research studies how guarantees on path quality can be provided after only a finite amount of computation. This results in probabilistic near-optimality in finite time, which yields a confidence interval that solutions will be found with bounded length relative to true optimal paths. This work also seeks to extend these properties to sparse roadmap methods to provide this property using compact roadmap representations.
The increasing availability of low-cost, compliant and human-friendly manipulators allows robots to share a common workspace and cooperate with human workers. It is important that the human is able to easily understand the robot's intentions by observing its actions. Legible motion plans are important to make the robot understandable by human and it has been investigated previously with two reachable targets. The current study is to expand upon the existing experimental studies in two primary directions. First, it considers a workspace with multiple targets. Second, human behavioral experiments are performed. It confirms aspects of previous work - the contradictory nature of shortest and legible paths. They also reveal important features of legible paths in cluttered scenes.
The complexity of path planning problems increase exponentially with the dimensionality of the problem instance. Multi-Robot Path Planning problems have dimensionality linear to the number of agents planned for, quickly rendering complete, coupled methods to solve the problem intractable. This work shows how to intelligently couple agent interactions to produce complete planners which only require polynomial computation time. The focus is to create methods which are efficient, scale well to large problem instances, and are guaranteed to work on as many different problem instances as possible.
When there are multiple robots in the same, constraining environment, computing paths which allow all of the robots to reach their goals can become problematic. In such situations, a game-theoretic approach can be taken, where self-interested agents must coordinate in order to achieve their goals. In particular, this work investigates the use of a regret minimization framework. In the regret minimization framework, the robots do not need to know other robot's goals, making it an appropriate approach for a decentralized solution, since it allows the robots to prune certain actions with no inter-robot communication requirements.
This work focuses on decentralized solutions to multi-robot coordination and coherence problems using minimal communication. The coordination problems investigated involve systems which move with a minimum velocity, providing an efficient solution known as the Extended Roundabout Policy (ERP) which avoids livelock and deadlock situations. For team coherence, it is important for robots in a team to maintain communication with one another. Extending the Velocity Obstacle (VO) framework, this work applies a new type of constraint in the velocity space, called Loss of Communication Obstacles (LOCOs).
One approach for planning with dynamics is the framework of sampling-based kinodynamic algorithms, such as the popular RRT method. These methods aim to cover as quickly as possible the state space through sampling. Specifically the RRT algorithm makes use of an implicit Voronoi bias when selecting states and controls to expand a reachability tree into the state space. This favorable bias, however, is no longer available if there is no good distance metric in the state space or if drift and other dynamic constraints introduce undesired biases. This work tries to learn these biases and account for them in the sampling process.
Planning for teams of dynamically-constrained systems adds a great deal of difficulty to the motion planning problem. This work shows how planning for teams of dynamical systems, such as cars, can be done in a distributed and safe manner. Furthermore, it investigates how to maintain communication between the robots during an exploration task. The approach has the robots first generate a large set of candidate paths, and then performs path coordination between the systems. During the planning and coordination steps, the robots reason over sets of inevitable collision states and inevitable loss of communication states.
An interesting multi-robot motion planning challenge is to control a group of robots so as to maintain a formation, especially when the robots have motion constraints. This work investigates frameworks for maintaining formations using curvilinear coordinate systems. This work addresses how the motions of each robot constrain the others in the formation, as well as investigates how formations can be dynamically changed. By changing the formation, a team of robots can reach different parts of the space, such as moving single-file to navigate a narrow passageway. To accomplish this, a multi-level roadmap with each level representing a different static formation is precomputed.
Sampling-based roadmap techniques are highly parallelizable methods, allowing construction of roadmaps in a distributed manner. Tree-based methods, however, have many difficulties to overcome to achieve good parallel performance, such as requiring each node to share information about the tree constructed by other nodes. This work focuses on effectively bringing the benefits of roadmap-based construction to tree-based methods, and allow for powerful parallel sampling-based techniques to be used, helping the methods solve difficult problem instances by allowing many processors to find paths through difficult parts of the space, known as narrow passages.
Individuals with visual impairment face many difficult challenges when navigating in an unfamiliar environment. Many environments do not provide helpful haptic feedback structures for such individuals. This work focuses on developing a system for navigating individuals through an unfamiliar environment, using feedback from the user, modeled as a sort of sensor. The objective then is to generate instruction sets which allow navigating the user to their desired destination with a high degree of accuracy, using advanced filtering procedures and extensive study into how direction provision changes the effectiveness of navigating in an unfamiliar environment.
This work focuses on the creating robust indoor localization methods using only wireless ethernet access points. This problem presents several difficulties, and it is known that localization based on wireless routers can often lead to fairly large error. There are many ways to reduce the error generated in such a localization method, and this work shows that this error can be significantly reduced using a two-step process. The most important impact of the work is that accurate localization for indoor environments can be achieved using only off-the-shelf hardware, meaning the proposed localization methods are straightforward to employ in a wide variety of venues.
Path planning for a large number of robots in a centralized manner is a generally infeasible problem. This work instead focuses on using existing infrastructure in the environment to perform distributed, decoupled path planning for multi-robot path planning. The method does so without using priorities, and using sensors in the environment which use only local information. The result proves robust, reducing the number of deadlocks as opposed to other distributed approaches, and allows for computation to be performed on the cloud while only communicating basic direction provision to each of the robots.
Oftentimes, robot navigation schemes rely on having accurate distance information in the form of laser-range scanners or sonar. This work focuses on navigation using only bearing information, rather than using distance information. The robot can accurately determine the relative bearing of landmarks in its environment using a panoramic camera. Using this bearing information, the robot is able to execute a long and complex trajectory in order to complete some desired task and then return to its original position with a high degree of accuracy. This work focuses on the theoretical guarantees provided under an ideal model and proves navigability in two-dimensional workspaces under this model.
This work focuses on studying the problem of bearing-only Simultaneous Localization and Mapping (SLAM) for robotic systems using only bearing information. A deep and wide study into different approaches to the problem is given, investigating methods such as the Extended Kalman Filter (EKF), Expectation Maximization (EM), and Particle Filtering. This work shows that particle filters work particularly well, especially when extra steps are taken to improve their robustness to outliers.