Oktay Arslan, Alex Cunningham, Philip Rogers
This project will add new passing capabilities to the GT Robojackets RoboCup Small Size League (SSL) robot team. The existing system supports moving, shooting, and can play the rules of soccer well, but does not currently handle multirobot activity, such as passing, in a reliable manner. We will extend the current system to implement a robust offensive passing system where the robots will acquire ball control and then make a coordinated series of passes until it can shoot on goal. This combines a number of planning areas, in that the robots will need to handle real-time motion planning in order to coordinate passes, use graph-based search techniques to create plans, replan as the environment changes, and perform all of these tasks while in the presence of both an intelligent adversary and significant measurement uncertainty.
- "STP: Skills, tactics and plays for multi-robot control in adversarial environments" Brett Browning, James Bruce, Michael Bowling, and Manuela Veloso, Journal of System and Control Engineering (2005). This paper is the primary technique used by top RoboCup teams for planning both locally (kicking) and globally (passing) in the soccer domain. We have a rudimentary implementation of the STP framework currently, but it does not support global planning at the level required for competitive play. One of the main goals of our project is to extend our existing implementation, as the STP paper describes, to support passing and generally improved global teamplay.
- "Multi-robot team response to a multi-robot opponent team" James Bruce, Michael Bowling, Brett Browning, and Manuela Veloso, ICRA '03. This paper describes the CMDragons implementation of Skills, Tactics, and Plays (STP) framework, and how they use it to achieve teamwork plays such as passing. It presents an example of their playbook, which is also published in full online, and can be used as a starting point for our passing implementation. The CMDragons team uses extensive passing, including "One-touch" kicking and chip-kick passing.
- "Playing Creative Soccer: Randomized Behavioral Kinodynamic Planning of Robot Tactics" Stefan Zickler, Manuela Veloso, Proceedings of the RoboCup Symposium 2008, July 2008. This paper examines combining local and global planning into a unified framework. The traditional STP framework is essentially a FSM, and their proposed algorithm introduces nondeterminism to that framework, which allows them to combine the local ball/player dynamics with the global goals. This allows for impressive planning that can consider adversarial players, the physical constraints of each player, and advanced ball plays such as bouncing the ball off of other players into the goal. This framework allows for advanced passing configurations, which we would like to explore (such as 3-robot passing, which STP teams such as Skuba would have difficulty executing.)
- "Real-Time Randomized Path Planning for Robot Navigation" James Bruce, Manuela Veloso, IROS '02. This paper describes a modification the RRT algorithm called "execution extended RRT" (ERRT) that improves the efficiency of the RRT algorithm by weighting the search-space and improving replanning. Both of these topics are directly applicable to the RoboCup domain, where adversarial players affect the search space, and replanning is constantly occurring. By using ERRTs, our goal is to be able to create more efficient plans at the local planning level, which will lead to improved global plans.
- "Map-based Multiple Model Tracking of a Moving Object" Cody Kwok, Dieter Fox, Proceedings of RoboCup Symposium, 2004. Due to the camera position, it is common to lose track of the soccer ball when multiple robots are occluding the camera's view. This paper presents a Rao-Blackwellized Particle Filter (RBPF) for tracking of the ball. It uses a technique of using particle filters for the non-linear portion of the tracking, and an Extended Kalman Filter (EKF) for the linear portions. Examples of the non-linear ball dynamics are during kicking, bouncing, etc. We hope this will improve overall planning, and is a requirement for passing.
RoboCup Team Descriptions - Robocup requires that top teams publish an "Extended Team Description" describing their approach and techniques used. Each of the following teams have implemented extensive teamwork, including passing:
- "Skuba 2009 Extended Team Description" The Skuba team's planning is based on the STP framework with a simple method of passing based on "Positions" (such as Aggressor and Defender.) They have implemented a new position called "SpecialOp" that assists either a defender (SpecialOpDefender) or aggressor (SpecialOpAggressor) and allows passing between the regular position and the SpecialOp assistant.
- "CMDragons 2009 Extended Team Description" The CMDragon team uses a hierarchical control system framework. The three major components of the soccer behavior control system are: (1) world state evaluation and play selection; (2) skills and tactics; (3) navigation. The passing system has some predefined passing options (one-touch pass-and-shoot, pass-receive-turn-shoot, partial chip-pass variants) and use a passing evaluation function by using some metrics to select one of them.
Existing GaTech RoboCup Work
- GT Robojackets RoboCup SSL Team "Team Page" We will work with the existing platform, which includes a full simulator and a team of functioning robots for this project.
- RoboCup SSL League "General Page" The general domain description is here.
In as much detail as possible, describe your proposed work. Separate this description into the planning (autonomous decision making) challenges and others. Make sure to include both the problems you will be solving and the methods you expect to use to solve those problems.
- Planning Challenges
- What about your problem makes it interesting from the perspective of planning. What challenges will you encounter that basic planners / motion planners / controllers do not address.
This project is an interesting planning challenge because of the speed of the robots and play that occurs in these games. Unlike the humanoid or four-legged-leagues, the Small Size League (SSL) robots are extremely fast in both motion and shooting, which makes the soccer games fast-paced, and reliant on effectively solving a number of sophisticated planning challenges simultaneously. To implement a basic passing system, the robots need to be able to move and plan in their space effectively, which is a non-trivial challenge because the robots have high enough acceleration to flip themselves over if they stop too quickly. Once a robot has a ball, the other robots need to position themselves to both receive an incoming pass and make another pass. While the number of robots is relatively small, such that a simple graph search can produce a series of passes to shoot on goal, handling the dynamic conditions of a high-speed game forces the planner to be more sophisticated. Because this is a soccer game, the primary 'obstacles' on the field are not just static or even dynamic obstacles, they are adversarial robots that will attempt to disrupt any plan execution that occurs. An effective planner in for these challenges must simultaneously manage basic motion planning for the robots, model passing sufficiently well to pass between the robots, find and replan optimal positions for robots. The additional constraint on the system is the uncertainty of the measurement, as there is noise in the robot position measurements, and especially the ball, which will disappear off of the global vision system if it moves too fast - a scenario that occurs almost every time a shot is made.
- Proposed Solutions
- How will your work address these challenges. Be as specific as possible
We will develop a full-team passing system that will start as soon as our team regains ball control and continue until the ball is lost or our team scores a goal. The basic framework is that as soon as one of our robots has the ball, the planner will determine how to position the remaining robots to optimize their position to both receive the pass, make another pass, or make a shot on goal. The planner will also need to account for the defensive capabilities of the solution, as if a pass fails, then the robots need to also be arranges so as to avoid giving the opposing team a clear shot at our goal.
The basic planning system will function at low level by combining two-robot passes into more complex passing behaviors. In this case, two robot passing has the following steps:
- Preparation - Getting in position to make the pass
- Passer intercepts the ball and positions to shoot the ball towards the receiver
- Receiver drives towards target position
- Final shot decision - both robots must know where the intended destination of the ball and receiver is, but the pass will need to go to the position where the receiver will be when the ball arrives, not where the receiver currently is.
- Passer executes shot calculation to finalize aiming and shot power for the target destination
- Receiver uses the final destination to plan a trajectory to intercept the ball when it is shot
- Execute the shot - note that the camera is likely to lose the ball when it moves fast
- Passer shoots when the ball is ready
- Receiver needs to be ready to intercept and also adjust for real ball trajectory to catch the pass
- Receive the pass - by this point, the passer is already moving to its next role. The receiving robot needs to be properly aimed to regain ball control, catch the ball, and then begin the process again.
This basic structure that allows two robots to pass can then be used in a more general context to allow passing between all of the robots. As development continues, this passing structure will need to be heavily parameterized to allow for a variety of passing conditions. We will also optimize the timing so that there is no waiting for robots to get into position to either aim or receive a pass, as during this time other robots will have moved to intercept the pass. In the best case, passing will resemble one-touch passing, where there is no dribbling of the ball between receiving a pass and the next pass.
With a robust two-robot passing system, and the data collected as to how to make it work properly, it will be more possible to make reliable shot calculations for pass viability, which can then be used by a higher-level planner to determine what series of passes/shots can be used to move the ball around the opponent robots and make a shot on goal.
As a baseline comparison, we still have the 2009 Season RoboCup code, which will provide a useful basis for comparison with our new offence system, as the 2009 system had a relatively robust defence, and an offence that can be exploited by using passing. A successful offensive passing system should add enough robustness to the system to enable consistent wins against the 2009 system.
- Implementation Challenges
- What other problems do you expect to face in your implementation? Will you need some kind of robot hardware / software / sensors? Will you need to solve any problems in addition to planning.
Because this system is based on the existing technology developed by the GT RoboCup SSL team, we have a number of resources at our disposal, including a single team of robots, a software control system that implements basic motion control and basic behaviors, and a full simulator capable of using realistic physics. Because there is only one team of robots available, the majority of work will be in simulator, with smaller scale demos with real robots to ensure that passing works properly with physical hardware. In addition to planning, we will also improve the world modeling and game state identification systems to be more robust and allow for better play selection and adaptation - in particular, we need to track the ball more effectively.
- Proposed Algorithms
- What algorithms will be required to make these tools useful to your planner? How will you acquire them / implement them?
One algorithm frequently used for these systems is the Extended RRT, which incorporates probabilistic information into an RRT planner, such that the planner can account for possible failure to reach a goal in a probabilistic fashion. This additional RRT planner can be included among the existing utilities (such as basic shot calculators and RRT motion planning), and can be used at multiple levels: not only can we use ERRTs in basic two-robot systems, we can also use ERRTs for some of the global planning to handle shot and motion strategy. As an extension of RRTs, we anticipate being able to implement ERRTs ourselves and integrate them with the rest of the system.
|Week 1||Improve infrastructure, RBPF Ball Tracker, ERRT implementation||Skeleton for changes in week 2-7.|
|Week 2||Develop 2-robot scenarios and basic offense play||Construct the basic play and fundamental behaviors||RBPF Ball Tracker (matlab)|
|Week 3||Continue 2-robot passing development||Test and parameterize 2-robot system||RBPF Ball Tracker (C++)|
|Week 4||Develop full-team passing system and test scenarios||Test and parameterize 2-robot system, general Soccer code improvement, global optimization.||low-level path optimization.|
|Week 5||Continue full-team passing development||Get up and running on Soccer source structure?||Test and tune the passing system, improve interface.||low-level path optimization|
|Week 6||Evaluation against old RoboCup Team and results||Continue testing, integrating SQP optimizer||Shot solution calculator (high-level planning), 2-robot tests, generating high-level plans.|
|Week 7||Finalize project and presentation||Integrating SQP optimizer||Improving assumptions to make analytical solutions better, improving execution robustness.|
- Philip finished an implementation of a new ball tracker based on the paper Map-based Multiple Model Tracking of a Moving Object by Cody Kwok and Dieter Fox. It features several "modes" that the ball can be in, such as none, kicked, etc.
Still to do is to implement this code in the full simulation.
- Worked on cleanup of the software to remove much of the more rigid existing structure and make the system more expressive.
- Worked on executing simple robot passing.
- Performed cleanup of the Robocup software, to handle a more robust hierarchical behavior system.
- Created a gamestate identification module that determines the state of the game and labels certain conditions for decision-making later
- We have completed a new ball tracker and implemented it in our software.
- With help from several people on the Robocup team, we also have some test scenarios where our robots can successfully execute a pass command.
- As shown above, it is now possible to select plays directly from the GUI.
We also sketched out the high-level structure of our global passing technique. More images coming next week!
Current System State
In order to perform robust, efficient passing, we have decided on a particular structure for the offense play. The basic concept is that if there is a shot available or a sequence of passes to a shot (henceforth known as a "shooting solution"), then the system will construct the sequence of paths for robots and kicks, run a nonlinear optimization technique to improve the path and ensure viability, and then execute it.
This plan came out of two particular observations:
- This bypasses the existing RRT-based planner, which is too unpredictable in timing for highly coordinated actions. We have no particularly good way of telling when a robot will reach a location when using RRTs.
- Because of the particular scenario of robot soccer, we know there are a small number of obstacles on the field, and there are only a small number of possible paths between them. With an optimization algorithm, we can take a simple path and improve it to make it faster.
The resulting system structure for the offensive passing algorithm has the following structure:
* Shot solution calculator: Given the positions of all the robots and the ball, it is possible to determine if there is a shot solution available with a simple weighted graph search. This can be a simple heuristic for shot viability, or a more sophisticated system as necessary.
* Analytic planner: given a sequence of actions (e.g., pass-pass-shoot) the planner will form an initial plan to complete the solution. This will largely determine directions of travel around obstacles and a rough sequence.
* Optimization engine: with an initial estimate of a plan, the optimization engine will be able to create a graphical model of the plan and optimize for an optimal sequence of actions. The particular optimization engine is a nonlinear constrained optimization algorithm primarily designed for Simultaneous Localization and Mapping, but we will exploit the duality between this planning problem (create an optimal path from constraints) and SLAM (recover a previously traveled path given measurements).
* Underlying planner: given a previously optimized plan, the system will execute the plan.
The optimization algorithm comes from the gtsam library developed in the RIM center with Frank Dellaert, and is derived from Sequential Quadratic Programming. This algorithm is robust to both nonlinear systems and constraints, and has been reformulated to work in a graphical model environment, which allows for an intuitive construction of stochastic switched hybrid systems.
At the moment, the optimization engine is complete, and the shot solution calculator and analytic planner are in progress. We are still experimenting with the underlying planner as to how it can be modified to accept pre-created plans.
Analytic plans generated and executed successfully.
Working on improving optimization, robustness, and fixing bugs.
Improved initial plans considerably: