Decision Making and Learning for Robotics

The Robotic Decision Making Laboratory develops planning, coordination, and learning techniques for systems of mobile robotic sensors. At the core of robotics is the optimization of physical plans for tasks such as grasping and navigation. In contrast, a pervasive notion in engineering and computer science is the idea of information optimization. In our research, we seek to unify information optimization and physical motion planning to bridge the gap between the near-optimal performance possible in the digital world and the limited performance currently possible in the physical world.

Our goal is to develop robotic decision making techniques grounded in principled theoretical analysis capable of operating in changing and unstructured environments with imperfect information. We employ formal methods from machine learning, combinatorial optimization, approximation algorithms, and information theory to analyze the hardness of problems and derive techniques with guarantees on performance. Such techniques must be scalable, distributed, and adaptive for operation in the physical world.

Please note, this page has not been updated for some time. For an updated list of publications, please check here:
RDML publications page

Past Projects
Machine Learning for Robotic Environmental Monitoring
Autonomous Inspection and 3D Structure Mapping
Communication-aware Planning and Coordination
Multi-robot Search in the Physical World
EMBER: Robotics in Emergency Response
Personal Robotics
Aerial Search and Rescue
Emotion-based Social Robotics
Miniature Inspection Systems Technology

Machine Learning for Robotic Environmental Monitoring

An important problem for environmental science, biology, and climatology is the prediction of ocean processes based on historical data and ocean models. Available predictive models provide accurate prediction of ocean processes, but they typically do not provide confidence estimates of these predictions. We propose prediction methods based on Gaussian Process (GP) regression, which provide improved estimates of ocean currents and also have the potential to provide confidence bounds on these estimates. We demonstrate experimental validation on ocean current estimates from the Southern California Bight provided by the Regional Ocean Modeling System (ROMS) dataset, and we integrate these predictions into probabilistic planners to improve the safety of operation of autonomous underwater vehicles. Our techniques show potential for significantly improving the prediction of ocean processes for environmental monitoring applications.

Ocean currents in the Southern California Bight predicted using non-parametric Bayesian regression.

Risk map shows predicted shipping lanes that should be avoided to improve the safety of mobile robots operating in the open ocean

Publications:

Autonomous Inspection and 3D Structure Mapping

This project is focused on improving the inspection of structures and aging facilities through informed planning methods. We have examined this general problem in the domain of underwater inspection of a submerged ship hull with an autonomous underwater vehicle (AUV). The goal is to construct an accurate 3D model of the structure in order to detect any anomalies or deformations. This research focuses on the active setting, where the vehicle selects a path of viewing locations to improve a metric of inspection performance.

Our work formulates the inspection planning problem as an extension to Bayesian active learning, and we have shown connections to recent theoretical guarantees in this area. We have rigorously analyzed the benefit of adaptivity for such problems, and proved that the potential benefit of adaptivity can be reduced from exponential to a constant factor by changing the problem from cost minimization with a constraint on information gain to variance reduction with a constraint on cost. Such analysis allows the use of robust, non-adaptive algorithms that perform competitively with adaptive algorithms. Based on the analysis, our work proposed a method for constructing 3D meshes from sonar-derived point clouds, and introduced uncertainty modeling through non-parametric Bayesian regression. Finally, we demonstrated the benefit of active inspection planning using sonar data from ship hull inspections with the Bluefin-MIT Hovering AUV.

Hovering Autonomous Underwater Vehicle (HAUV) inspecting a ship hull.

Mesh reconstruction of the ship hull along with the planned path for the HAUV; red areas are areas of high uncertainty that require additional inspection.

Publications:

Communication-aware Planning and Coordination

Another important research thread related to robotic information gathering is the development of planning methods that properly utilize communication models to improve data collection in mobile networked systems. Along these lines, this project has examined the problem of utilizing an autonomous underwater vehicle (AUV) to collect data from an underwater sensor network. The sensors in the network are equipped with acoustic modems that provide noisy, range-limited communication. The AUV must plan a path that maximizes the information collected while minimizing travel time or fuel expenditure.

This research has proposed AUV path planning methods that extend algorithms for variants of the Traveling Salesperson Problem (TSP). While executing a path, the AUV can improve performance by communicating with multiple nodes in the network at once. Such multinode communication requires a scheduling protocol that is robust to channel variations and interference. To this end, we examined two multiple access protocols for the underwater data collection scenario, one based on deterministic access and another based on random access. We compared the proposed algorithms to baseline strategies through simulated experiments that utilize models derived from experimental test data. The results demonstrate that properly designed communication models and scheduling protocols are essential for choosing the appropriate path planning algorithms for data collection.

Pictorial representation of a network of underwater gliders in the coastal ocean

 A SeaBed class AUV being deployed to perform underwater data collection.

 Publications:

Multi-robot Search in the Physical World

This project examined the broad problem domain of search in the physical world, which differs significantly from the searches in the digital world that we perform every day on our computers. When searching the internet, for instance, success is a matter of informed indexing that allows the information to be retrieved quickly. In these cases, there is no consideration of the physical nature of the world, and the search is not cognizant of space, time, or traversal distance. In contrast, search in the physical world must consider a target that could be continuously moving, possibly even trying to evade being found. The environment may be partially known, and the search proceeds with information gathered during the search itself. In many cases, such as guaranteeing capture of an adversarial target, the problem cannot be solved with a single searcher, and all group members must coordinate their actions with others on the team. Prior work had explored limited instances of such problems, but existing techniques either scaled poorly or did not have performance guarantees.

This project considered two of the main variations of search in the physical world: efficient search and guaranteed search. During efficient search, robots move to optimize the average-case performance of the search given a model of the target’s motion. During guaranteed search, robots coordinate to minimize the worst-case search time if the target is adversarial. This work unified these search problems and showed them to be NP-hard, which suggests that a scalable and optimal algorithm is unlikely. In addition, we showed that efficient search admits a bounded approximation, and guaranteed search does not. Despite these hardness results, algorithms using implicit coordination can provide scalable and high-performing solutions to many real-world search problems. Implicit coordination is defined as the sharing of locations, measurements, and/or actions to improve the team plan. In accord with this design strategy, this work presented a linearly scalable efficient search algorithm that utilizes implicit coordination to achieve bounded performance. In addition, we contributed a novel approach that augments the coordination with a pre-search spanning tree generation step, which leads to an anytime algorithm for guaranteed search.

Autonomous ground vehicles searching an outdoor urban environment for a mobile intruder.

 Office and museum maps used for adversarial search; the spanning tree representation guides robotic searchers to guarantee capture of any target in the building.

 Publications:

EMBER: Robotics in Emergency Response

The goal of this project was to assist first responders in emergency situations by providing tracking information and situational awareness. In these harsh and dynamic situations, there is no guarantee of a communication infrastructure or access to GPS. Therefore, to provide tracking and coordination, we need to deploy our own infastructure.

The Ember project utilized multi-agent teams, comprised of autonomous and human agents, to achieve effective results under emergency situations. Agents used wireless networks for communication in order to achieve difficult team-oriented tasks. In the firefighting scenario, a key technology is the ability to track the firefighter and provide accessible communciation to prevent dangerous situations. The goal of the robot team is to track the firefighter, while at the same time, leaving;adequate communication links back to the base station.

Volunteer firefighter searching a building with a Pioneer robot. The robot provides localization information and situational awareness to the firefighter.

Publications:

Personal Robotics

In collaboration with Intel Research Pittsburgh, this project explored the interconnection between search and action in the context of mobile robotics. The task of searching for an object and then performing some action with that object is important in many applications. Of particular interest is the idea of a robot assistant capable of performing worthwhile tasks around the home and office (e.g., fetching coffee, washing dirty dishes, etc.).

This project analyzed the search/action problem formally and proved that some tasks allow for search and action to be completely decoupled and solved separately, while other tasks require the problems to be analyzed together. In addition to theretical analysis, we designed a combined search/action approximation algorithm that draws on prior work in search. We showed the effectiveness of the algorithm by comparing it to state-of-the-art solvers, and we provided empirical evidence showing that search and action can be decoupled for some useful tasks. Finally, we demonstrated the approach on a Home Exploring Robot Butler (HERB) performing object search and delivery in an office environment.

The Home Exploring Robot Butler (HERB) locating a coffee mug. The vehicle autonomously searches for the mug in a complex office environment.

HERB returns the coffee mug to the sink using autonomous navigation capabilities.

Publications:
  • S. Srinivasa, D. Ferguson, C. Helfrich, D. Berenson, A. Collet, R. Diankov, G. Gallagher, G. Hollinger, J. Kuffner, and J.M. Vande Weghe, "Herb: A home exploring robotic butler," Autonomous Robots (AURO), vol. 28, no. 1, pp. 5-20, Jan. 2010.
  • G. Hollinger, D. Ferguson, S. Srinivasa, and S. Singh, "Combining search and action for mobile robots," in Proc. IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan, May 2009, pp. 952-957. Video.

Aerial Search and Rescue

This project proposed construction of a lighter-than-air robotic blimp for use in an urban search and rescue environment. The blimp uses an onboard wireless camera, sonar, and infrared sensors to perform tasks both autonomously and under teleoperated joystick control. During autonomous flight, the blimp is capable of both following lines on the floor and wandering without collision. Additionally, the blimp is equipped with a marker deployment servo to allow the user to mark victims that he or she has identified with the camera. The blimp uses a modular software architecture with separate processes controlling wireless communication, navigation, and vision. Ultimately, this design shows the potential for the use of aerial robots in indoor search and rescue environments.

Indoor robotic blimp designed for urban search and rescue tasks. Our blimp won the autonomy portion of the Drexel Aerial Robotics Competition (2005).

Publications:

Emotion-based Social Robotics

This project examined the problem of buliding a robot that interacts with humans in a crowded conference environment. The robot detects faces, determines the shirt color of onlooking conference attendants, and reacts with a combination of speech, musical, and movement responses. It continuously updates an internal emotional state, modeled realistically after human psychology research. Using empirically-determined mapping functions, the robot’s state in the emotion space is translated to a particular set of sound and movement responses. We successfully demonstrated this system at the AAAI ’05 Open Interaction Event, showing the potential for emotional modeling to improve human-robot interaction.

Social mobile robot demonstrated at AAAI 2005. The robot uses emotion-based mechanisms to determine its actions and to better interact with onlookers.

Publications:

Miniature Inspection Systems Technology

In collaboration with NASA's Marshall Space Flight Center, this project developed a miniature robot to inspect pipes both on Earth and in zero-gravity. Using the Darwin2k development software, a genetic algorithm (GA) was employed to design and optimize a pipe-crawling robot for parameters such as mass, power consumption, and joint extension to further the research of the Miniature Inspection Systems Technology (MIST) team. In an attempt to improve on existing designs, a new robot was developed, the piezo robot. The final proposed design uses piezoelectric expansion actuators to move the robot with a ‘chimneying’ method employed by mountain climbers and greatly improves on previous designs in load bearing ability, pipe traversing specifications, and field usability.

In complementary work, we utilized a GA to design fault-tolerant analog controllers for the piezoelectric micro-robot. We developed first-order and second-order functions to model the robot’s piezoelectric actuators, and the GA was used to evolve closed-loop controllers for both models. Fault-tolerance was built into the fitness function to facilitate the design of controllers robust to both actuator failure and component failure. The GA was successfully used to design synthetic controllers and to optimize a traditional PID design. This research shows the advantages of GA assisted design when applied to robotic design and control problems.

Pip-crawling inspection robot with design specifications found using a genetic algorithm.

Fault-tolerant analog control designed using a genetic algorithm and utilized for the pipe-crawling robot.

Publications: