MultiRobot Lab Mobile Autonomous Robot Software (MARS)

Project Objectives

We remain focused on our objectives of:

Develop complete, effective and scalable software for autonomous robot teams. Demonstrate robot teams with integrated perception, reasoning, learning, communication and cooperative strategies that solve complex multi-agent tasks.

Project Website

More details on our project and copies of our presentations are available on the project website: http://www.cs.cmu.edu/~multirobotlab/MARS

Approach

Adversarial multi-robot problems, where teams of robots compete with one another, require the development of approaches that span all levels of control and integrate algorithms ranging from low-level robot motion control, through to planning, opponent modeling, and multi-agent learning. Our research is primarily focused on addressing such multi-robot control issues in task-driven adversarial environments. In particular, we demonstrate much of our work within the context of robot soccer; a task-driven domain involving unknown adversaries in a dynamic and uncertain environment.

Under the MARS program, we continue to focus on the key challenges for building individually skilled autonomous robots and successful multi-robot teams to operate in uncertain, adversarial domains. These challenges range from single robot issues of localization, real-time visual sensing, robust tracking, high-speed navigation control, and automatic segmentation and recognition of environmental regimes through to multi-robot team issues of adaptive team strategy, robust cooperation through communication in the face of uncertainty, and team learning. All of these issues are important to the successful operation of multi-robot teams.

We recently competed at the RoboCup-2002 world robot soccer championships, winning first prize in the legged league competition. Additionally, we demonstrated our research during the DarpaTech Symposium held during July. More details on these events are listed in the recent accomplishments. Our recent research focuses on:

Adaptive Team Strategy
For multi-robot teams in adversarial settings, good individual skills must be employed within the team's high-level strategy to be effective. This strategy should emphasize the team's strengths while simultaneously exploiting the opponent's weaknesses. We have developed an adaptive architecture that customizes the team strategy on-line and in real-time to enhance the overall performance of the team.

Our playbook strategy engine fulfills three goals concurrently. To coordinate team behavior, to provide an easy human and/or automated augmentation of the team strategy and to facilitate on-line adaptation to an opponent. The playbook engine achieves each of these goals through the use of plays. Each play contains a set of roles for each member of the team, and a set of predicates that determine when that particular play is applicable. Roles are assigned dynamically to team members based on evaluation heuristics e.g. closest to the ball. Each role contains a simple temporal plan; a series of high-level parametrized actions that player should perform. Thus each play concisely encodes a short sequence of coordinated team activity for a particular situational context. Plays are stored as human readable text files with a format that is easy to read, create, and modify as required.

The most interesting innovation, is that play selection is adaptive. A play is selected to be the active play based in part on its applicability and upon a weight that translates into its probability of selection. Our playbook engine adaptively adjusts the play selection probabilities based upon the performance of the play against the given opponent as measured by a small set of reward criteria. The reward criteria includes both positive and negative reward conditions such as a goal scored for or against us. With this approach, play selection adapts over the duration of a game (ie within minutes) to select plays that work the best against the given opponent. (IROS workshop paper, see list below, further papers forthcoming)

Teamwork communication and collaboration
Since the recent availability of wavelan to support wireless communication for our Sony AIBOs, we have been investigating algorithms and representations for collaborative behavior between autonomous legged robots. This work represents a unification and extension of our prior work with the Sony AIBO's and our minnow team for distributed cooperation via communication.

We have developed algorithms for building a global world model that is jointly maintained across the team. Each robot shares with the team their own high-level local perception output along with the associated measures of uncertainty. Building on our prior work in distributed sensing, our algorithms effectively fuse the information reliably while handling uncertainty and conflict resolution in a principled manner. The resulting global map enables us to estimate the confidence of our model, to predict future states of the world, and extend each robot's effective perception range beyond the capabilities of any single robot. (paper forthcoming)

Based on the fused global model, we have build team coordination algorithms. Our robots position themselves by a gradient ascent function in a field of constraints and objectives; they spread out on the field assuming roles of attacker, supporter, and defender in positions that are suitable to carry out tasks in line with that role. (paper forthcoming)

Localization
In our previous work under the MARS program, we developed Sensor Resetting Localization (SRL), an extension to Monte-Carlo probablistic localization techniques. Because effective robots may be small, they can be moved by external sources beyond the robot's own control. The SRL algorithm that we devised allows robots to use their sensor input to rapidly adapt to changes in their position. The robots effectively localize in real-time with an accuracy of 2-5 cm. Although effective, SRL still requires heavy computational resources given the position belief computation for its large number of sample points.

Continuing our commitment to effective real-time localization, we have investigated new localization algorithms that attempt to address the multi-sample problem. We developed a localization algorithm, Constraint Based Localization (CBL), which maintains a single belief of the robot's location updated by its sensor input and movement. CBL is computationally more efficient than SRL and is more robust through its use of multiple landmarks. Our latest algorithms have been implemented on different robot platforms. (Various publications, see list below)

High-speed navigation and control
High-speed navigation is a poorly explored area of robotics research and yet there are many robotics problems that require high-speed navigation for them to be effective. To date, it is a commonly accepted belief that high-speed navigation can only be addressed by a combination of low-level reactive navigation algorithms driven by high-level planning algorithms. Our recent work has proven this belief to be incorrect.

We have extended the Rapidly-Exploring Random Trees (RRT) planning algorithm and applied it to controlling our team of five small-size robots (average computation time is 2ms per robot) moving at speeds of up to 1.7m/s through cluttered, moving obstacles fields. The algorithm works by progressively building a search tree through a combination of random exploration and biased motion towards the goal state. Our extensions to the basic RRT algorithm include:

• A KD-tree representation for fast nearest neighbor search
• A way-point cache for fast re-planning with similar initial and target states
• Low-level predictions to compensate for moving obstacles
• Post-planning path smoothing to produce a follow-able path for the robot

Preliminary comparisons against conventional reactive navigation schemes indicate that it can control the robot at significantly higher speeds without requiring significant computational resources. (IROS'02 publication, see list below)

Generalized vision-based obstacle avoidance
We have developed a new vision processing algorithm, built upon our CMVision library (see http://www.cs.cmu.edu/~jbruce/cmvision), to perform general (ie. any shape or color) obstacle avoidance. The algorithm operates on our Sony AIBO's at the full frame-rate of 25Hz on a 200MHz MIPs processor. The algorithm, which we call visual sonar, calculates the radial distances to objects around the robot regardless of the robot's head or body orientation. (paper forthcoming)

Real-time visual sensing and tracking
In order for our robots to react sensibly to changes in the real world, they must be able to quickly sense objects in their environment. We have extended our previously developed color vision library, called CMVision (see http://www.cs.cmu.edu/~jbruce/cmvision for details) to process images at the full available frame rate with low CPU usage. Moreover, CMVision is cross platform and operates on our Sony AIBO's as well. Additionally, we have developed new techniques to improve the robustness of multi-agent tracking in the face of false-positive recognitions. This technique has applications in systems where false-positives must be dealt with using a minimal amount of computational resources. (ICRA'02 publication, see list below)

Automatic segmentation and recognition of environmental regimes
Robot environments are typically quasi-stationary systems. Being able to identify and recognize the different environmental regimes or contexts offers the ability to extend the use and dynamic range of many current algorithms significantly. We are developing algorithms to automatically segment and recognize different sensory inputs using on-line, non-parametric statistical tests. Our current work focuses on learning to distinguish lighting level regimes in an office environment on a Sony Aibo. Once the lighting level is recognized, the appropriate thresholds for color image segmentation can be chosen thereby increasing the dynamic range of the color vision routines used by the robot. (paper forthcoming)

Our most recent accomplishments revolve around RoboCup-2002, the annual world robot soccer championships held this year in Fukuoka, Japan (see http://www.robocup2002.org for more information). With over 200+ teams from 30 different countries, along with 120,000 spectators over 5 days, this event continues to grow in popularity. Meanwhile, the competition level continues to improve at an ever increasing rate. This year, our development focussed on our Sony AIBO team, CMPack'02, and our small-size team, CMDragons'02. We demonstrated the capabilities of our multi-robot technologies in the best possible way: winning first place in the Sony legged league.

In order to create our teams of autonomous robots, we have investigated a number of issues that apply to any multi-robot team operating in an adversarial environment. In doing so, we have produced a number of publications reporting on our contributions which are listed at the end of this page.

Our specific accomplishments during the last reporting period are:


• CMPack'02: RoboCup-2002 Sony Legged Robot World Champions
  For the first time, the CMPack'02 team, which consists of four fully autonomous four-legged Sony AIBO robots, could communicate via a wireless network thereby presenting some tremendous research opportunities. We have extended our previous technological developments under the MARS program for sensor fusion and teamwork for the CMPack'02 team. Our effort includes:
  • A new vision processing algorithm, which we call visual sonar, that gives radial distances to the objects around the robot. (paper forthcoming)
  • extensions to our prior localization algorithms to improve robustness and computational speed. (papers at ICRA'00, IROS'02, another forthcoming)
  • Representations and algorithms for a collaborative building of a global world model, where robots share with each other their own local perception; our algorithms effectively address the problem of sensor information fusion, handling uncertainty, prediction, confidence, and conflict resolution. (paper forthcoming)
  • Multi-robot team coordination our robots position themselves on the field driven by a gradient ascent function in a field of constraints and objectives; they spread beautifully on the field assuming roles of attacker, supporter, and defender. They communicate among themselves crucial information for the coordination. (paper forthcoming)
  • Faster, more robust, and more accurate robot motion (possible undergraduate senior thesis forthcoming)
• CMDragons'02: RoboCup-2002 Smallsize League Quarter Finalists
  For the first time in any robot league at RoboCup, our team adapted its play during each game to customize its strategy against each opponent. We have developed a playbook strategy engine that enables team coordination, easy generation of new coordinated plays by a human or computer, and adapts its use of the plays during the game based on performance. Specifically, our development effort includes:
  • The development of the playbook strategy engine and its use in competition. Quantitative assessment of its capabilities is planned. (paper forthcoming)
  • The development of high-speed planning algorithms for navigating in cluttered, moving, obstacle fields. Our algorithm, based on Rapidly Exploring Random Trees, is sufficiently fast that each planning cycle takes on average 2ms. Thus we can control a team of five robots at 30Hz while performing vision, strategy, and motion control computations. (see publication list)
  • The development of high-speed motion control algorithms to support our fast navigation planning. (paper forthcoming)
  • The extension of our fast, robust color vision library and computationally efficient probabilistic tracking algorithms for observing and tracking 11 objects moving at high speeds (the ball sometimes exceeds 6m/s). (see publication list) crap
• Demonstrations at DarpaTech'02 held in Anaheim, California during late July. At this event, we presented both of our robot soccer teams CMPack'02 and CMDragons'02. To demonstrate the robustness and versatility of the algorithms, we had the robots perform a variety of different tasks including:
  • Various games of legged robot soccer between two CMPack'02 teams of up to 3 robots each.
  • Various games of small-size robot soccer between two CMDragon'02 teams of up to 5 robots each.
  • Humans vs small-size robots where one or two humans uses hockey sticks against the CMDragons'02 team of 3 to 5 robots.
  • Obstacle avoidance of any general obstacle by a Sony legged robot.
  • Collaborative ball collection using two Sony legged robots and up to 8 balls.
• We have developed a new technique for automatic segmentation and recognition of environmental regimes. We have validated the approach on a Sony Aibo robot platform. The robot is able to recognize, on-line, different lighting regimes and select the appropriate vision calibration parameters to enable it to see reliably. (paper forthcoming)

Plan

During the FY02, we will continue our research on learning on autonomous teams of robots in several different areas, including concretely:
• Task 1: Principled techniques for robust teamwork via communication with uncertain information.
  It is clear that cooperation via explicit communication is significantly more powerful than cooperation without communication. However, robustly integrating teamwork mechanisms with communication where the information is intermittent, possibly latent, and its quality is uncertain, is a difficult challenge. There are many sources of uncertainty. Information is often noisy, and due to limits on perception and errors in modeling conflicts can arise between the world models of each robot. Thus, principled techniques are required to resolve conflicts and reduce uncertainty in communication between teammates and to be able to use this information effectively in order to realize the true potential of multi-robot teams. We have already made significant progress towards this goal over the past year. We will continue to work with our robot soccer teams towards achieving this goal.
• Task 2: Building truly multi-robot, real-time plans for controlling fast moving teams of robots.
  We have already developed a fast, real-time planning algorithm for controlling an individual robot in a moving, dynamic world. However, much can still be done towards truly multi-robot planning where plans for an entire team, rather than just for individual robots, are cooperatively determined. Although effective, our planning techniques are still susceptible to causing undue interference between teammates. We will investigate extensions to our planning algorithm to facilitate true multi-robot planning where interference between teammates in minimized.
• Task 3: Investigation of techniques for automated, on-line, environment regime recognition.
  Our initial work with automated recognition of environmental regimes has focused on recognizing temporal changes in one-dimensional sensory data using a small set of clearly distinguished regimes. We will extend our work to include multi-dimensional sensory data and a larger set of environmental regimes. Additionally, we will examine ways to extend our approach to operate with different rates of context switches. That is, environmental changes can be categorized based upon their temporal duration. Some changes a fleeting, while other take substantially longer to occur. Being able to recognize environmental changes regardless of their temporal duration can significantly extend the operation range of many standard algorithms. Indeed, this is one of our primary aims: to extend the operational capacity of well understood algorithms through recognition of the environment context.
• Task 4: Extending our play strategy engine to investigate learning plays, and more advanced play adaptation.
  Strategy adaptation is a key skill for both single- and multi-agent systems. We have developed, under the MARS program, techniques for adapting a set of pre-defined plays, or strategies, to improve the performance against a given opponent. We will further investigate this approach, with a focus towards developing algorithms to learn plays from prior experience and observations of opponent games.

Technology Transition

All of our software and research publications will continue to be available on the net. A number of our programs are already on-line and have been used by a number of researchers world-wide. In particular, our fast color vision library CMVision has proven popular amongst many roboticists in the research community. Future web releases and publications are planned.

The following robot designs and software funded under the MARS program have been developed by us and released to the community:

• Our real-time color vision library CMVision
• Our main robot soccer web site: Carnegie Mellon Robot Soccer
• Our Sony Aibo robot soccer web site: CMPack'02
• Our small-size robot soccer web site: CMDragons'02

Relevant Publications

• Multiagent learning using a variable learning rate, Michael Bowling and Manuela Veloso. Artificial Intelligence 136:215-250, 2002.
• Real-time randomized path planning for robot navigation, James Bruce and Manuela Veloso. In Proceedings of IROS-2002, Switzerland, October 2002. An earlier version of this paper appears in the Proceedings of the RoboCup-2002 Symposium.
• Scalable learning in stochastic games, Michael Bowling and Manuela Veloso. In Proceedings of the AAAI-2002 Workshop on Game Theoretic and Decision Theoretic Agents, Edmonton, Canada, August 2002.
• Improbability Filtering for Rejecting False Positives, Brett Browning, Michael Bowling, and Manuela Veloso. In Proceedings of ICRA-02, the 2002 IEEE International Conference on Robotics and Automation, Washington, DC, May 2002.
• Fast Parametric Transitions for Smooth Quadrupedal Motion, James Bruce, Scott Lenser, and Manuela Veloso. In A. Birk, S. Coradeschi, and S. Tadokoro, editors, RoboCup-2001: The Fifth RoboCup Competitions and Conferences. Springer Verlag, Berlin, 2002.
• A modular hierarchical behavior-based architecture, Scott Lenser, James Bruce, and Manuela Veloso. In A. Birk, S. Coradeschi, and S. Tadokoro, editors, RoboCup-2001: The Fifth RoboCup Competitions and Conferences. Springer Verlag, Berlin, 2002.
• CM-Pack'01: Fast Legged Robot Walking, Robust Localization, and Team Behaviors William Uther, Scott Lenser, James Bruce, Martin Hock, and Manuela Veloso. In A. Birk, S. Coradeschi, and S. Tadokoro, editors, RoboCup-2001: The Fifth RoboCup Competitions and Conferences. Springer Verlag, Berlin, 2002.
• Convergence of gradient dynamics with a variable learning rate, Michael Bowling and Manuela Veloso. In Proceedings of ICML-2001, pages 27--34, Williams College, MA, June 2001.

---

Manuela Veloso
Last modified: 7 August 2002