- Tools
- Important Classes
- Protobuf
- Design Patterns
- Coroutines
- Finite State Machines
- Conventions
- Architecture Overview
- Simulator
- GUI
A few commonly-used terms and tools to be familiar with:
- This is the shared vision system used by the Small Size League. It is what connects to the cameras above the field, does the vision processing, and transmits the positional data of everything on the field to our AI computers.
- The GitHub repository can be found here
- Sometimes referred to as the "Referee", this is another shared piece of Small Size League software that is used to send gamecontroller and referee commands to the teams. A human controls this application during the games to send the appropriate commands to the robots. For example, some of these commands are what stage the gameplay is in, such as
HALT,STOP,READY, orPLAY. - The GitHub repository can be found here
These are classes that are either heavily used in our code, or are very important for understanding how the AI works, but are not core components of the AI or other major modules. To learn more about these core modules and their corresponding classes, check out the sections on the Backend, Sensor Fusion, AI, and Visualizer.
The World class is what we use to represent the state of the world at any given time. In this context, the world includes the positions and orientations of all robots on the field, the position and velocity of the ball, the dimensions of the field being played on, and the current referee commands. Altogether, it's the information we have at any given time that we can use to make decisions.
A team is a collection of Robots
A Robot class represents the state of a single robot on the field. This includes its position, orientation, velocity, angular velocity, and any other information about its current state.
The Ball class represents the state of the ball. This includes its position and velocity, and any other information about its current state.
The Field class represents the state of the physical field being played on, which is primarily its physical dimensions. The Field class provides many functions that make it easy to get points of interest on the field, such as the enemy net, friendly corner, or center circle. Also see the coordinate convention we use for the field (and all things on it).
These represent the current state of the game as dictated by the Gamecontroller. These provide functions like isPlaying(), isHalted() which tell the rest of the system what game state we are in, and make decisions accordingly. We need to obey the rules!
An Intent represents a simple thing the AI wants (or intends for) a robot to do, but is at a level that requires knowledge of the state of the game and the field (e.g. Referee state, location of the other robots). It does not represent or include how these things are achieved. Some examples are:
- Moving to a position without colliding with anything on its way and while following all rules
- Pivoting around a point
- Kicking the ball at a certain direction or at a target
There are two types of Intents: DirectPrimitiveIntents and NavigatingIntents. DirectPrimitiveIntents directly represent the Primitives that the AI is trying to send to the robots. NavigatingIntents are intents that require moving while avoiding obstacles, so they contain extra parameters to help with Navigation.
Dynamic Parameters are the system we use to change values in our code at runtime. The reason we want to change values at runtime is primarily because we may want to tweak our strategy or aspects of our gameplay very quickly. During games we are only allowed to touch our computers and make changes during halftime or a timeout, so every second counts! Using Dynamic Parameters saves us from having to stop the AI, change a constant, recompile the code, and restart the AI.
Additionally, we can use Dynamic Parameters to communicate between the Visualizer and the rest of our system. The Visualizer can change the values of DynamicParameters when buttons or menu items are clicked, and these new values will be picked up by the rest of the code. For example, we can define a Dynamic Parameter called run_ai that is a boolean value. Then when the Start [AI](#ai) button is clicked in the Visualizer, it sets the value of run_ai to true. In the "main loop" for the AI, it will check if the value of run_ai is true before running its logic.
Here's a slightly more relevant example of how we used Dynamic Parameters during a game in RoboCup 2019. We had a parameter called enemy_team_can_pass, which indicates whether or not we think the enemy team can pass. This parameter was used in several places in our defensive logic, and specifically affected how we would shadow enemy robots when we were defending them. If we assumed the enemy team could pass, we would shadow between the robots and the ball to block any passes, otherwise we would shadow between the enemy robot and our net to block shots. During the start of a game, we had enemy_team_can_pass set to false but the enemy did start to attempt some passes during the game. However, we didn't want to use one of our timeouts to change the value. Luckily later during the half, the enemy team took a time out. Because Dynamic Parameters can be changed quick without stopping AI, we were quickly able to change enemy_team_can_pass to true while the enemy team took their timeout. This made our defence much better against that team and didn't take so much time that we had to burn our own timeout. Altogether this is an example of how we use Dynamic Parameters to control our AI and other parts of the code.
It is worth noting that constants are still useful, and should still be used whenever possible. If a value realistically doesn't need to be changed, it should be a constant (with a nice descriptive name) rather than a Dynamic Parameter. Having too many Dynamic Parameters is overwhelming because there are too many values to understand and change, and this can make it hard to tune values to get the desired behaviour while under pressure during a game.
Protobuf or protocol buffers are used to pass messages between components in our system.
After building using Bazel, the .proto files are generated into .pb.h and .pb.cc files, which are found in bazel-out/k8-fastbuild/bin/proto.
To include these files in our code, we simply include proto/<protobuf_filename>.pb.h
These are protobuf messages that we define and that are important for understanding how the AI works.
TbotsProto::Primitives represent simple actions that robots blindly execute (e.g. send signals to motor drivers), so it's up to the AI to send Primitives that follow all the rules and avoid collisions with obstacles. Some examples are:
- Moving in a straight line to a position
- Pivoting around a point
- Kicking the ball at a certain direction
Primitives act as the abstraction between our AI and our robot firmware. It splits the responsibility such that the AI is responsible for sending a Primitive to a robot telling it what it wants it to do, and the robot is responsible for making sure it does what it's told. For every Primitive protobuf message, there is an equivalent Primitive implementation in our robot firmware. When robots receive a Primitive command, they perform their own logic and control in order to perform the task specified by the Primitive.
The TbotsProto::RobotStatus protobuf message contains information about the status of a single robot. Examples of the information they include are:
- Robot battery voltage
- Whether or not the robot senses the ball in the breakbeam
- The capacitor charge on the robot
- The temperature of the dribbler motor
Information about the robot status is communicated and stored as RobotStatus protobuf messages. The Visualizer displays warnings from incoming RobotStatuses so we can take appropriate action. For example, during a game we may get a "Low battery warning" for a certain robot, and then we know to substitute it and replace the battery before it dies on the field.
Below are the main design patterns we use in our code, and what they are used for.
Abstract classes let us define interfaces for various components of our code. Then we can implement different objects that obey the interface, and use them interchangeably, with the guarantee that as long as they follow the same interface we can use them in the same way.
Read [https://www.geeksforgeeks.org/inheritance-in-c/] for more information.
Examples of this can be found in many places, including:
The Singleton pattern is useful for having a single, global instance of an object that can be accessed from anywhere. Though it's generally considered an anti-pattern (aka bad), it is useful in specific scenarios.
Read [https://www.tutorialspoint.com/Explain-Cplusplus-Singleton-design-pattern] for more information.
We use the Singleton pattern for our logger. This allows us to create a single logger for the entire system, and code can make calls to the logger from anywhere, rather than us having to pass a logger object literally everywhere.
The Factory Design Pattern is useful for hiding or abstracting how certain objects are created.
Read [https://www.geeksforgeeks.org/design-patterns-set-2-factory-method/] for more information.
Because the Factory needs to know about what objects are available to be created, it can be taken one step further to auto-register these object types. Rather than a developer having to remember to add code to the Factory every time they create a new class, this can be done "automatically" with some clever code. This helps reduce mistakes and saves developers work.
Read [http://derydoca.com/2019/03/c-tutorial-auto-registering-factory/] for more information.
The auto-registering factory is particularly useful for our PlayFactory, which is responsible for creating Plays. Every time we run our AI we want to know what Plays are available to choose from. The Factory pattern makes this really easy, and saves us having to remember to update some list of "available Plays" each time we add or remove one.
The Factory pattern is also used to create different Backends
The Visitor Design Pattern is arguably the most "advanced" design pattern we use. It is used when we need to perform different operations on a group of "similar" objects, for example a bunch of objects that inherit from the same parent class (Intents). We might only know all these objects are an Intent, but we don't know specifically which type each one is (eg. MoveIntent vs KickIntent). The Visitor Pattern helps us "recover" that type information so we can perform different operations on the different types of objects. It is generally preferred to a big if-block with a case for each type, because the compiler can help warn you when you've forgotten to handle a certain type, and therefore helps prevent mistakes.
Read [https://www.geeksforgeeks.org/visitor-design-pattern/] for more information.
Examples of the Visitor Pattern can be found with the following classes:
The Observer Design Pattern is useful for letting components of a system "notify" each other when something happens. Read [https://www.geeksforgeeks.org/observer-pattern-set-1-introduction/] for a general introduction to the pattern.
Our implementation of this pattern consists of two classes, Observer and Subject. Observers can be registered with a Subject, after which new values will be sent from each Subject to all of it's registered Observers. Please see the headers of both classes for details. Note that a class can extend both Observer and Subject, thus receiving and sending out data. In this way we can "chain" multiple classes.
In our system, we need to be able to do multiple things (receive camera data, run the AI, send commands to the robots) at the same time. In order to facilitate this, we extend the Observer to the ThreadedObserver class. The ThreadedObserver starts a thread with an infinite loop that waits for new data from Subject and performs some operation with it.
WARNING: If a class extends multiple ThreadedObservers (for example, AI could extend ThreadedObserver<World> and ThreadedObserver<RobotStatus>), then there will be two threads running, one for each observer. We do not check for data race conditions between observers, so it's entirely possible that one ThreadedObserver thread could read/write from data at the same time as the other ThreadedObserver is reading/writing the same data. Please make sure any data read/written to/from multiple ThreadedObservers is thread-safe.
One example of this is SensorFusion, which extends Subject<World> and the AI, which extends ThreadedObserver<World>. SensorFusion runs in one thread and sends data to the AI, which receives and processes it another thread.
While debatably not a design pattern depending on who you ask, templating in C++ is a powerful tool that is very useful to understand. [https://www.geeksforgeeks.org/templates-cpp/] gives a great explanantion and example.
We use templating in a few places around the codebase, with the most notable examples being our Factory Design Patterns, and our Gradient Descent optimizer.
Coroutines are a general control structure where the flow control is cooperatively passed between two different routines without returning, by allowing execution to be suspended and resumed. This is very similar to the yield statement and generators in Python.
Rather than using the return keyword to return data, coroutines use the yield keyword. The main difference is that when return is encountered, the data is returned and the function terminates. If the function is called again, it starts back from the beginning. On the other hand, when yield is encountered some data is returned, but the state of the function / coroutine is saved and the function does not terminate. This means that when the function is called again, execution resumes immediately after the yield statement that previously returned the data, with all the previous context (variables, etc) as if the function never stopped running. This is the "suspend and resume" functionality of coroutines.
See the following C++ pseudocode for an example. This coroutine function computes and returns the fibonacci sequence.
int fib(Coroutine::push_type& yield) {
int f1 = 1;
int f2 = 0;
while(true) {
int fn = f1 + f2; // Compute the next value in the sequence
f2 = f1; // Save the previous 2 values
f1 = fn;
yield(fn);
}
}
int main() {
// Coroutine setup stuff
// Lets pretend that we have created the Coroutine and called it `yield`
std::cout << fib(yield) << std::endl; // Prints 1
std::cout << fib(yield) << std::endl; // Prints 2
std::cout << fib(yield) << std::endl; // Prints 3
std::cout << fib(yield) << std::endl; // Prints 5
std::cout << fib(yield) << std::endl; // Prints 8
// and so on...
}
Lets walk through what's happening here:
- The first time the
fibfunction is called, the variablesf1andf2are initialized, and we go through the first iteration of the loop untilyieldis encountered - The
yieldstatement is going to return the currently computed value of the fibonacci sequence (the variablefn) and save the state of thefibfunction- "yielding" the data here is effectively returning it so that the code in the
mainfunction can print the result
- "yielding" the data here is effectively returning it so that the code in the
- The second time
main()calls thefib()function, the function will resume immediately after theyield()statement. This means that execution will go back to the top of the loop, and still remember the values off1andf2from the last time the function was called. Since the coroutine saved the function state, it still has the previous values off1andf2which it uses to compute the next value in the sequence. - Once again when the
yield()statement is reached, the newly computed value is returned and the function state is saved. You can think of this as "pausing" the function. - As
main()keeps calling thefib()function, it is computing and returning the values of the fibonacci sequence, and this only works because the coroutine "remembers" the values from each previous fibonacci computation which it uses to compute the next value the next time the function is called.- If the
yieldwas replaced with a regularreturnstatement, the function would only ever return the value1. This is because usingreturnwould not save the function state, so the next time it's called the function would start at the beginning again, and only ever compute the first value of the sequence.
- If the
This example / pseudocode does hide away some details about how coroutines are set up and how we extract values from them, but it's most important to understand how coroutines change the flow of control in the program.
We use the boost Coroutine2 library. Specifically, we use Asymmetric Coroutines.
This stackoverfow answer gives a decent explanation of the difference between Symmetric and Asymmetric Coroutines, but understanding the difference is not critical for our purposes. We use Asymmetric Coroutines because boost does not provide Symmetric Coroutines, and the hierarchical structure of Asymmetric Coroutines is more useful to us.
We use Coroutines to write our strategy logic. The "pause and resume" functionality of Coroutines makes it much easier to write Plays.
Specifically, we use Coroutines as a way to break down our strategy into "stages". Once a "stage" completes we generally don't want to re-evaluate it, and would rather commit to a decision and move on. Coroutines makes it much easier to write "stages" of strategy without requiring complex state machine logic to check what stage we are in, and it's easier for developers to see what the intended order of operations is (eg. "Line up to take the shot" -> "shoot").
In the past, we had issues with our gameplay logic "committing" to decisions if we were near certain edge cases. This caused robots to behave oddly, and sometimes get significantly slowed down in "analysis paralysis". Coroutines solve this problem by allowing us to write "stages" that execute top-to-bottom in a function, and once we make a decision we commit to it and move on to the next stage.
Here's a more specific example. In this example we are going to pretend to write a Tactic that will pass the ball.
def executeStrategy(IntentCoroutine::push_type& yield, Pass pass) {
do {
yield(/* align the robot to make the pass */)
}while(current_time < pass.start_time);
do {
yield(/* kick the ball at the pass location */)
}while(/* robot has not kicked the ball */)
}
We will pretend that this function is getting called 30 times per second to get the most up-to-date gameplay decision.
In this example, each do while() loop is a "stage". When the function is first called, we enter the first stage. In this stage, we will keep telling the robot to line up behind the ball to be ready to make the pass. The robot will continue to do this until it is time to start the pass.
Once it is time to start the pass, the condition for the loop will become false and we will exit the loop. Then we enter the second loop / stage. The second stage tells the robot to kick the ball, and this continues until the ball has been kicked. Once the ball has been kicked, the loop will terminate and the function will end because the execution reaches the end of the function.
Once we have entered the second stage, we know we don't have to look at the first stage again. Because the coroutine "remembers" where the execution is each time the function is called, we will resume inside the second stage and therefore never execute the first stage again! This makes it much easier to write and read this strategy code, because we can clearly see the 2 stages of the strategy, and we know they will be executed in order.
Coroutines are a complex feature, and the boost coroutines we use don't always behave in was we expect. We have done extensive testing on how coroutines are safe (or not safe) to us, and derived some best practices from these examples. See coroutine_test_exmaples.cpp for the full code and more detailed explanantions.
To summarize, the best practices are as follows:
- Avoid moving coroutines. If the absolutely must be moved, make sure they are not moved between the stack and heap.
- Avoid using coroutines with resizable containers. If they must be used, make sure that the coroutines are allocated on the heap.
- Pass data to the coroutine on creation as much as possible, avoid using member variables.
A finite state machine (FSM) is a system with a finite number of states with defined transitions and outputs based on the inputs to the system. In particular, we are interested in hierarchical state machines where we can transition between states in terms of when states should transition (guards) and what should happen when transitions occur (actions), given a specific input (event). Hierarchical state machines are state machines that are composed of one or more FSMs, which we call sub-FSMs. The parent FSM can treat a sub-FSM as a state with guards and actions when transitioning to and from the sub-FSM. When the sub-FSM enters a terminal state, the parent FSM is able to automatically transition to another state.
We use the Boost-Ext SML, short for State Machine Library, to manage our finite state machines. This library defines state machines through a transition table, where a row indicates the transition from one state to another subject to guards, actions and events. The syntax of a row of the transition table looks like this:
src_state + event [guard] / action = dest_state
where the src_state transitions to the dest_state, while performing the action, only if the event is processed and the guard is true. Events are structs of new information that FSMs receive, so guards and actions take events as arguments. Guards must return a boolean and actions must return void. An asterix (*) at the start of a row indicates that the state is an initial state. The rows of the transition table are processed in order and the first row to match is executed.
The library also supports hierarchical FSMs. Sub-FSMs are treated as states where an unconditional transition occurs when the sub-FSM is in the terminal state, X.
/* omitted rows of transition table */
SubFSM = next_state, // Transitions to next_state only when the SubFSM is in the terminal state, X
/* omitted rows of transition table */
In order to update a subFSM with an event, we need to do the following:
const auto update_sub_fsm_action =
[](auto event, back::process<TypeOfSubFSMEvent> processEvent) {
TypeOfSubFSMEvent sub_fsm_event = // initialize the subFSM event
processEvent(sub_fsm_event);
};
The convenience of this syntax comes at the cost of hard to read error messages due to the functor and templating system.
We use SML to manage our Tactics. Each state represents a stage in the tactic where the robot should be doing a particular action or looking for certain conditions to be true. An example of this is the MoveFSM. While the robot is not at the destination and oriented correctly, the FSM is in the move state. Once the robot reaches its destination, it enters the terminal state, X, to indicate that it's done. SML also allows us to easily reuse FSMs in other tactics. For example, if a shadowing tactic needs to move to a particular destination with a certain orientation, then it can use the MoveFSM as a sub-FSM state.
Boost-ext SML is a library that supports complex functionality with similarly complex syntax and semantics. If complex syntax is misused, the complicated error messages can make development difficult. Thus, we need to carefully choose a standardized subset of the library's syntax to implement our functionality while maintaining high readability.
- Only use one event per FSM: In gameplay, we react to changes in the World, so since there's only one source of new information, we should only need one event
- Only one guard or action per transition: For readability of the transition table, we should only have one guard or action per transition. This can always be achieved by defining a guard or action outside of the transition table that checks multiple conditions or performs multiple actions if that's required.
- Define guards and actions outside of the transition table: The names of guards and actions should be succinct so that transition tables rows fit on one line and readers can easily understand the FSM from the transition table. In other words, no lambdas/anonymous functions in transition tables.
- States should be defined as classes in the FSM struct so that users of the FSM can check what state the FSM is in:
// inside the struct
class KickState;
// inside the operator()()
const auto kick_s = state<KickState>;
// allows for this syntax
fsm.is(boost::sml::state<MyFSM::MyState>)
- Avoid entry and exit conditions: Everything that can be implemented with entry and exit conditions can easily be implemented as actions, so this rule reduces source of confusion for the reader
- Avoid self transitions, i.e.
src_state + event [guard] / action = src_state: self transitions call entry and exit conditions, which complicates the FSM. If we want a state to stay in the same state while performing an action, then we should use an internal transition, i.e.src_state + event [guard] / action. - Avoid orthogonal regions: Multiple FSMs running in parallel is hard to reason about and isn't necessary for implementing single robot behaviour. Thus, only prefix one state with an asterix (*)
- Use callbacks in events to return information from the FSM: Since the SML library cannot directly return information, we need to return information through callbacks. For example, if we want to return a double from an FSM, we can pass in
std::function<void(double)> callbackas part of the event and then make the action call that function with the value we want returned. - When a variable needs to be shared between multiple states or can be initialized upon construction of the FSM, then define a private member and constructor in the FSM struct, and pass that in when constructing the FSM. Here's a code snippet:
(drive_forward_fsm.h)
DriveForwardFSM
{
public:
DriveForwardFSM(double max_speed): max_speed(max_speed){}
private:
double max_speed;
}
(drive_forward_tactic.h)
FSM<DriveForwardFSM> fsm;
(drive_forward_tactic.cpp: constructor)
fsm(DriveForwardFSM(10.0))
Various conventions we use and follow that you need to know.
We use a slightly custom coordinate convention to make it easier to write our code in a consistent and understandable way. This is particularly important for any code handling gameplay logic and positions on the field.
The coordinate system is a simple 2D x-y plane. The x-dimension runs between the friendly and enemy goals, along the longer dimension of the field. The y-dimension runs perpendicular to the x-dimension, along the short dimension of the field.
Because we have to be able to play on either side of a field during a game, this means the "friendly half of the field" will not always be in the positive or negative x part of the coordinate plane. This inconsistency is a problem when we want to specify points like "the friendly net", or "the enemy corner". We can't simple say the friendly net is (-4.5, 0) all the time, because this would not be the case if we were defending the other side of the field where the friendly net would be (4.5, 0).
In order to overcome this, our convention is that:
- The friendly half of the field is always negative x, and the enemy half of the field is always positive x
yis positive to the "left" of someone looking at the enemy goal from the friendly goal- The center of the field (inside the center-circle) is the origin /
(0, 0)
This is easiest to understand in the diagram below.
Based on what side we are defending, Sensor Fusion will transform all the coordinates of incoming data so that it will match our convention. This means that from the perspective of the rest of the system, the friendly half of the field is always negative x and the enemy half is always positive x. Now when we want to tell a robot to move to the friendly goal, we can simply tell it so move to (-4.5, 0) and we know this will always be the friendly side. All of our code is written with the assumption in mind.
Going along with our coordinate convention, we have a convention for angles as well. An Angle of 0 is along the positive x-axis (facing the enemy goal), and positive rotation is counter-clockwise (from a perspective above the field, looking at it like a regular x-y plane where +y is "up"). See the diagram below.
Because of our Coordinate Conventions, this means that an angle of 0 will always face the enemy net regardless of which side of the field we are actually defending.
At a high-level our system is made of 4 main components: The Backend, the Sensor Fusion, the AI, and the Visualizer. These 4 components each run in their own thread, and communicate with each other using the Observer design pattern.
The Backend is responsible for communicating with the outside world (network and radio), Sensor Fusion is responsible for processing and filtering raw data, the AI makes the actual gameplay decisions, and the Visualizer shows us what's happening and lets us control the AI.
Each component is described in more detail in their own sections.
The Backend is responsible for all communication with the "outside world". The responsibilities of the Backend can be broken down into communication using SensorProto and Primitives messages:
-
Upon receiving the following messages from the network (outside world), the
Backendwill store it in aSensorProtomessage and send it to Sensor Fusion:- Robot status messages
- Vision data about where the robots and ball are (typically from SSL-Vision)
- Referee commands (typically from the SSL-Gamecontroller
-
Upon receiving Primitives from the AI,
Backendwill send the primitives to the robots or the Simulator.
The Backend was designed to be a simple interface that handles all communication with the "outside world", allowing for different implementations that can be swapped out in order to communicate with different hardware / protocols / programs.
Sensor Fusion is responsible for processing the raw data contained in SensorProto into a coherent snapshot of the World that the AI can use. It invokes filters to update components of World, and then combines the components to send out the most up-to-date version.
Filters take the raw data from SensorProto and returns an updated version of a component of the World. For example, the BallFilter takes BallDetections and returns an updated Ball.
- Why we need to do this: Programs that provide data like SSL-Vision only provide raw data. This means that if there are several orange blobs on the field, SSL-Vision will tell us the ball is in several different locations. It is up to us to filter this data to determine the "correct" position of the ball. The same idea applies to robot positions and other data we receive.
Filters provide a flexible way to modularize the processing of raw data, making it easy to update filters and add new ones. Filters are sometimes stateful. For example, the BallFilter "remembers" previous locations of the ball in order to estimate the ball's current velocity.
The AI is where all of our gameplay logic takes place, and is the main "brain" of our system. It uses the information received from Sensor Fusion to make decisions, and sends Primitives to the Backend for the robots to execute. All together this feedback loop is what allows us to react to what's happening on the field and play soccer in real-time.
The 2 main components of the AI are strategy and navigation.
We use a framework called STP (Skills, Tactics, Plays) to implement our stratgy. The STP framework was originally proposed by Carnegie Mellon University back in 2004. The original paper can be found here.
STP is a way of breaking down roles and responsibilities into a simple hierarchy, making it easier to build up more complex strategies from simpler pieces. This is the core of where our strategy is implemented.
When the AI is given new information and asked to make a decision, our STP strategy is what is executed first. It takes in a World and returns Intents.
The STP diagram shows how this works. Functions to assign tactics to robots and build motion constraints are passed into a Play's get function, which the Play uses to generate tactics with assigned robots and with updated motion constraints.
The T in STP stands for Tactics. A Tactic represents a "single-robots' role" on a team. Examples include:
- Being a goalie
- Being a passer or pass receiver
- Being a defender that shadows enemy robots
- Being a defender that tries to steal the ball from enemies
They can also represent lower level behaviours, such as
- Moving to a position (without colliding with anything)
- Shooting the ball at a target
- Intercepting a moving ball
The high level behaviours can use the lower level behaviours in a hierarchical way.
Tactics use Intents to implement their behaviour, so that it can decouple strategy from the Navigator.
The P in STP stands for Plays. A Play represents a "team-wide goal" for the robots. They can be thought of much like Plays in real-life soccer. Examples include:
- A Play for taking friendly corner kicks
- A Play for defending enemy kickoffs
- A general defense play
- A passing-based offense play
- A dribbling-based offense play
Plays are made up of Tactics. Plays can have "stages" and change what Tactics are being used as the state of the game changes, which allows us to implement more complex behaviour. Read the section on Coroutines to learn more about how we write strategy with "stages".
Furthermore, every play specifies an Applicable and Invariant condition. These are used to determine what plays should be run at what time, and when a Play should terminate.
Applicable indicates when a Play can be started. For example, we would not want to start a Defense Play if our team is in possession of the ball. The Invariant condition is a condition that must always be met for the Play to continue running. If this condition ever becomes false, the current Play will stop running and a new one will be chosen. For example, once we start running a friendly Corner Kick play, we want the Play to continue running as long as the enemy team does not have possession of the ball.
The Navigator is responsible for path planning and navigation. Once our strategy has decided what it wants to do, it passes the resulting Intents to the Navigator. The Navigator is then responsible for breaking down the Intents and turning them into Primitives.
DirectPrimitiveIntents are easy to break down into Primitives, and can be converted directly without having to do any extra work.
However, NavigatingIntents like the MoveIntent rely on the navigator to implement more complex behaviour like obstacle avoidance. In order for a robot to move to the desired destination of a NavigatingIntents, the Navigator will use various path-planning algorithms to find a path across the field that does not collide with any robots or violate any restrictions set on the NavigatingIntents. The NavigatingPrimitiveCreator then translates this path into a series of Primitives, which are sent to the robot sequentially so that it follows the planned path across the field.
The Path Manager is responsible for generating a set of paths that don't collide. It is given a set of Path Objectives and Path Planner, and it will generate paths using the given path planner and arbitrate between paths to prevent collisions.
A path objective is a simple datastructure used to communicate between the navigator and the path manager. It conveys information for generating one path, such as start, destination, and obstacles. Path Objectives use very simple datastructures so that Path Planners do not need to know about any world-specific datastructures, such as Robots or the Field.
The Path Planner is an interface for the responsibility of path planning a single robot around a single set of obstacles from a given start to a given destination. The interface allows us to easily swap out path planners.
AI Diagram
The Visualizer is exactly what it sounds like: A visualizion of our AI. It provides a GUI that shows us the state of the World, and is also able to display extra information that the AI would like to show. For example, it can show the planned paths of each friendly robot on the field, or highlight which enemy robots it thinks are a threat. Furthermore, it displays any warnings or status messages from the robots, such as if a robot is low on battery.
The Visualizer also lets us control the AI by setting Dynamic Parameters. Through the Visualizer, we can manually choose what strategy the AI should use, what colour we are playing as (yellow or blue), and tune more granular behaviour such as how close an enemy must be to the ball before we consider them a threat.
The Visualizer is connected to the rest of the system using the Observer Design Pattern. It observes Subjects that contain information it wants to display, such as the World or DrawFunctions.
The Visualizer is implemented using Qt, a C++ library for creating cross-platform GUIs. The general documentation for Qt can be found here. The most important parts for the Visualizer are:
- Signals and Slots
- QtCreator (specifically for Widget-based applications)
- Widgets
The Visualizer is made up of the following components:
- Qt Components
- The QApplication. This is the Qt component that manages the event loop and all the widgets in the GUI.
- The
Visualizer Widget. This contains all of the graphical components used in the Visualizer.
- Non-Qt Components
- The
VisualizerWrapper. TheVisualizerWrappercontains the QApplication andVisualizer Widget. It runs the QApplication in a separate thread, so that Qt can run its event loop and handle events and rendering without blocking our main thread.
- The
The VisualizerWrapper needs to communicate with the QApplication and Visualizer Widget running in its separate thread in order to trigger events like drawing when new data is received. In order to do this, the VisualizerWrapper and Visualizer Widget use our ThreadsafeBuffer class to communicate. The VisualizerWrapper pushes data into the buffers, and the Visualizer Widget pops the data in a Producer -> Consumer pattern. This means the Visualizer Widget can handle data at its own rate, independent from the VisualizerWrapper.
In some rare cases, we use the Qt MetaObject system to send signals to trigger functions in the Qt thread in a thread-safe way. This is further documented in the code.
Although we want to display information about the AI in the Visualizer, we cannot send copies of an AI object to the Visualizer over the Observer system because the AI is non-copyable. Draw Functions are our solution that allow us to draw information in the Visualizer for non-copyable types.
A DrawFunction is essentially a function that tells the Visualizer how to draw something. When created, DrawFunctions use lazy-evaluation to embed the data needed for drawing into the function itself. What is ultimately produced is a function that the Visualizer can call, with the data to draw (and the details of how to draw it) already included. This function can then be sent over the Observer system to the Visualizer. The Visualizer can then run this function to perform the actual draw operation.
Estop allows us to quickly and manually command physical robots to stop what they are doing. We have a couple of implementations of Estop, depending on which Backend is being used:
- For
WifiBackend, theEstopis a stateful switch connected to an Arduino. The switch state is communicated to theWifiBackendregularly. WhenEstopis in aSTOPstate, theWifiBackendoverrides the Primitives sent to the robot to anEstop primitive. when it is in aPLAYstate, primitives are communicated normally. - For
RadioBackend, TheEstopswitch is part of the Radio dongle, which is responsible for filtering out messages sent to the robots.
The Simulator is what we use for physics simulation to do testing when we don't have access to real field. In terms of the architecture, the Simulator "simulates" the following components' functionalities:
- SSL-Vision by publishing new vision data
- the robots by accepting new Primitives
Using the current state of the simulated world, the Simulator simulates the new Primitives over some time step and publishes new ssl vision data based on the updated simulated world. The Simulator is designed to be "perfect", which means that
- the vision data it publishes exactly reflects the state of the simulated world
- the simulation perfectly reflects our best understanding of the physics (e.g. friction) with no randomness.
The Simulator uses Box2D, which provides 2D physics simulation for free. While this simplifies the simulator greatly, it means that we manually implement the physics for "3D effects", such as dribbling and chipping.
The Standalone Simulator is a wrapper around the Simulator so that we can run it as a standlone application that publishes and receives data over the network. The Standalone Simulator is designed to interface with the WifiBackend over the network, and so it is essentially indistinguishible from robots receiving Primitives and an SSL-Vision client publishing data over the network. The Standalone Simulator also has a GUI that provides user-friendly features, such as moving the ball around.
When it comes to gameplay logic, it is very difficult if not impossible to unit test anything higher-level than a Tactic (and even those can be a bit of a challenge). Therefore if we want to test Plays we need a higher-level integration test that can account for all the independent events, sequences of actions, and timings that are not possible to adequately cover in a unit test. For example, testing that a passing play works is effectively impossible to unit test because the logic needed to coordinate a passer and receiver relies on more time-based information like the movement of the ball and robots. We can only validate that decisions at a single point in time are correct, not that the overall objective is achieved successfully.
Ultimately, we want a test suite that validates our Plays are generally doing the right thing. We might not care exactly where a robot receives the ball during a passing play, as long as the pass was successful overall. The solution to this problem is to use simulation to allow us to deterministically run our entire AI pipeline and validate behaviour.
The primary design goals of this test system are:
- Determinism: We need tests to pass or fail consistently
- Test "ideal" behaviour: We want to test the logic in a "perfect world", where we don't care about all the exact limitations of our system in the real world with real physics. Eg. we don't care about modelling robot wheels slipping on the ground as we accelerate.
- Ease of use: It should be as easy and intuitive as possible to write tests, and to understand what they are testing.
The SimulatedTestFixture consists of three components:
- A Simulator that does physics simulations based on the Primitives it receives
- A Sensor Fusion that processed raw data for the AI
- The AI under test
The components of this system are run in a big loop. The Simulator publishes new vision data with a fixed increment and that data is passed through Sensor Fusion to produced an updated World for the AI. The SimulatedTestFixture will wait to receive Primitives before triggering simulation and publishing the next World. This means that no matter how much faster or slower the simulation runs than the rest of the system, everything will always happen "at the same speed" from the POV of the rest of the system, since each newly published World will be a fixed amount of time newer than the last. See the section on Component Connections and Determinism for why this is important.
Validation Functions are the way we check that the behaviour of the AI is as we expect. They are essentially functions that contain Google Test ASSERT statements, and use Coroutines to maintain state. We can create a list of Validation Functions that are run every time SimulatedTestFixture produces an updated World, so that we can continuously check that the behaviour of the AI is as we expected. See the section on Component Connections and Determinism for how this is used and why this is important.
A Validation Function comes in two types:
- Terminating: Some sequence of states or actions that must occur in a given order and then terminate. (Eg. A robot moves to point A, then point B, and then finally kicks the ball)
- Non-terminating: Some condition that must be met for the entire duration of the test, i.e. "for all time". (Eg. The ball never leaves the field or all friendly robots follows SSL rules).
Benefits of Validation Functions:
- They are reuseable. We can write a function that validates the ball never leaves the field, and use it for multiple tests.
- They can represent assertions for more complex behaviour. For example, we can build up simpler
Validation Functionsuntil we have a singleValidationfunction for a specific Tactic. - They let us validate independent sequences of behaviour. For example, we create a different
ValidationFunctionfor each Robot in the test. This makes it easy to validate each Robot is doing the right thing, regardless if they are dependent or independent actions.
When testing, determinism is extremely important. With large integration tests with many components, there are all kinds of timings and execution speed differences that can change the behaviour and results. We make use of a few assumptions and connect our components in such a way that prevents these timing issues.
The Validation Functions are run before updating AI with a new World and getting new primitives so that we stop as soon as we know that there's incorrect behaviour. See the diagram.
Now we have a nice loop from the Simulator -> Sensor Fusion -> Validation Functions -> AI -> Simulator .... As mentioned in their own sections, the Simulator waits to receive Primitives from the AI before publishing a new World, and the Validation Functions wait to receive and validate a World allowing the new world to be published. The final assumption we make to complete this loop is that the AI waits to receive a new World before publishing new Primitives.
What this means is that each component in the loop waits for the previous one to finish its task and publish new data before executing. As a result, no matter how fast each component is able to run, we will not have any issues related to speed or timing because each component is blocked by the previous one. As a result, we can have deterministic behaviour because every component is running at the same speed relative to one another.
Notice this is very similar to the Architecture Overview Diagram, with the Backend replaced by the Simulator and with Validation Functions in the loop between Sensor Fusion and AI.
The Visualizer and connections to it are marked with dashed lines, since they are optional and are not run during the tests unless we are debugging.
When creating widgets in QtCreator, all widgets should be given a descriptive name. This is because the .ui file will eventually be generated into code that we interact with, so we want the variable names to be descriptive and consistent with our naming conventions.
Names should follow our reglar naming conventions for variables. Furthermore, they should be named in the form <purpose>_<widget>. The purpose is essentially the "normal" variable name that should describe what the variable is. The widget component should be the name of the widget.
For example, a QLabel for team colour should be named team_colour_label. Similarly, the button that starts the AI should be named start_ai_button.
Only the top-level class for a given GUI should be suffixed with GUI. These top-level classes should just aggregate top-level widgets (typically generated from a .ui file) and connect callbacks. They should not define additional widgets or features themselves. For example, FullSystemGUI connects incoming buffers of data to the main_widget generated by a .ui file.
Qt provides QtCreator, an IDE used for visually creating GUIs and laying out widgets. We use this editor as much as possible since it is easy to learn and use, and saves us having to define the entire GUI in code (which is more complex and makes things generally harder to understand and modify).
Our rule of thumb is that QtCreator should be used to define all the widgets in the Visualizer, and define the layout for everything. All logic (including connecting signals and slots, receiving data from buffers, etc.) should be implemented in the code ourselves.
For a very quick tutorial on how to use QtCreator, see this video
To summarize, QtCreator creates and modifies a .ui file, which is more-or-less an XML describing the GUI application (what components exist, how they are positioned relative to one another, and their attributes). During compilation, this .ui file gets generated into code which handles all the setup and layout of the GUI components that have been defined in the .ui file. We include the autogenerated code in our Visualizer code where we are then able to connect the autogenerated widgets to various functions, and implement the logic we need to.
- Open QtCreator
- Click
File -> Open File or Project - Select the
.uifile. - Make your changes (Don't forget to save. You must save the file for changes to be picked up in compilation)
The most important thing to know about editing the Visualizer in QtCreator, is how to promote generic widgets to custom widgets. If we want to extend a QtWidget with custom behavior, we need to create our own class that extends the Widget we want to customize. However, we would still prefer to use QtCreator to declare this widget and how it fits in the GUI layout.
"Promoting" a widget in QtCreator allows us to place a "generic" widget in the layout, and then tell QtCreator we actually want that widget to be our custom class. To promote a widget:
- Right-click the widget you want to promote
- Click
Promote ToorPromoted Widgets - Choose the custom widget this widget should be promoted to. Create a new promoted class if necessary.
- When creating new promoted classes, make sure to provide the path to the header file relative to the bazel
WORKSPACEfile. This will make the#includestatements in the generated code use the full path, which is required bybazel.
- When creating new promoted classes, make sure to provide the path to the header file relative to the bazel
More information about defining custom widgets in QtCreator can be found here.
Although this will focus on Qt-specific examples, these principles generally apply to all GUI design and implementation. They are really just Software Engineering principles applied to GUIs.
Qt is designed to handle hierarchy. It has an extensive and robust system for maintaining Object Trees and parent/child relationships between components. Much like regular code, GUIs should be created in a logical hierarchy to make organization and re-use easier.
Make sure to use layouts, and group widgets in a logical way. For example, several widgets that work together to collect a user's mailing address should be grouped. This group may then be part of a larger group of widgets in a popup dialog asking for billing information.
Here is a good example of laying out widgets in a hierarchy:
Do not lay out all your widgets in a single layer like this:
The main point to remember is to use layouts to group and manage widgets, and to create these groups in a logical way that can be built into a hierarchy. This will make it significantly easier to replace parts of the GUI later, or move components around.
Much like how we create functions in order to reuse code, widgets should be created so that they are reusable.
For example, if you create a few widgets that work together to gather user input with a slider and display the current value next to it, you should combine all of this into its own SliderWithValue widget. This will make it very easy to make several copies of this widget, or use it somewhere else in a completely different application. Similarly, if you need specialized functionality from any widget (for example, our ZoomableQGraphicsView), this should also be implemented as a custom reusable widget.
Creating widgets that are slightly more generic and reusable are very useful and allow code and graphical modules to be shared and reused between multiple applications.
- Define minimum and maximum sizes (if it makes sense) to help enforce the correct sizing of elements
- Eg. define a minimum width for a textbox based on what it's expected to contain