-
Notifications
You must be signed in to change notification settings - Fork 97
Communication Model Tutorial
The SubT communication model approximates how radio propagation works inside our subterranean environment. It's a probabilistic model that considers the topology of the path that needs to be traversed from source to destination, as well as the Euclidean distance between the robots involved in the communication. In addition, it supports the deployment of breadcrumbs, acting as repeaters extending the reach of the team’s communication. It's out of the communication model’s scope to simulate with high fidelity how radio propagation works in the real world. This includes reflections, losses due to different materials, or any other complex interaction of that nature.
The communication model is created by combining two different heuristics, each of them contributing a cost function to the global communication model. These two cost functions are mixed in a way that lets the communication model decide the probability of successful communication from a given source to a destination. The two cost functions are named "visibility" and "range". Next, we'll describe how each cost function is calculated, and then we'll detail how both functions are combined.
The purpose of this document is to give a detailed description of the communication model in order to set expectations about the communication model’s behavior. It's not the purpose of this document to provide a deep description of all the implementation details and parameters present in the model. For further details please refer to the source code.
This is a topological approach where we evaluate the complexity of the communication path from source to destination. For a given pair of robots (source and destination), the visibility cost function will return a non-negative number that expresses the visibility cost from the source robot to the destination. Intuitively, a low number means that both robots have good visibility, and vice versa. Let's now describe how the visibility cost function is calculated.
All SubT virtual environments are constructed using a combination of connected tiles. In this phase, we create an undirected graph where each tile is a node. When two adjacent tiles are traversable in simulation, we also create an edge between the corresponding nodes. Finally we assign a cost to that edge based on how complex are the two affected nodes. When the graph is calculated, it's saved as a <world_name>.dot file. Note that this is a well-known format for expressing graphs and can be visualized with tools like dot.
The next step is an optimization required to save processing time during simulation. The goal is to precompute which points in the 3D world are within the subterranean environment and store the tile that contains the point. We sample all the 3D space every cubic meter. If the sample point is traversable by a robot, we save it along with the ID of the tile (or the node in the graph) that contains the point. This information is saved in binary format as a <world_name>.dat file.
The previous two steps are executed offline, while this step is performed during simulation initialization. Here, we load the graph from step (1) and run Dijkstra for every pair of nodes. Additionally, we load the .dat file from step (2) in memory. After this we can return the visibility cost for a given pair of robots in two quick steps. First, we get the pose of the two robots involved and compute the tile ID where they're located. Then, we just need to use the information generated after running Dijkstra for getting the cost associated with the given pair of nodes in the graph. This number is our visibility cost.
This is a metric-based heuristic where we compute the Euclidean distance between source and destination.
When we have the visibility cost and the range cost for a given pair of robots, we combine them such that a Gaussian function is created. There are some additional parameters to set the impact of each cost function in the global model. Using this Gaussian distribution and a modulation scheme, we draw a value that will give the success or failure result of each communication attempt.
Note that there are other constraints that may cause the communication to fail. Examples of these constraints are visibility cost over a visibility threshold, range cost over a max distance threshold, maximum capacity of the channel reached, among others.
The communication model supports the notion of deploying a collection of breadcrumbs which may extend the effective communication range. The communication model is updated each time a breadcrumb is deployed.
In the presence of breadcrumbs, the visibility cost is modified as follows. The breadcrumb positions are obtained and from that we extract the tile IDs in which the breadcrumbs are contained. Next, the communication model evaluates whether it's possible to reach a destination using any number of breadcrumbs as intermediate relays. From the visibility point of view, each time that a message reaches a breadcrumb the visibility is reset to zero. Then, the message can continue until the destination tile or another breadcrumb is found. If the algorithm finds a path reaching the destination using N number of breadcrumbs, the visibility cost is the max cost of any intermediate segment. Intuitively, the visibility cost of the entire route is the cost of the worst segment. A segment is defined as the route between any pair of breadcrumbs or from source to the first breadcrumb, or from the last breadcrumb to the destination. If it's possible to reach the destination tile from different paths (maybe using a different sequence of breadcrumbs), the algorithm selects the route with lowest overall cost.
In a similar way, the range heuristic is also updated in the presence of breadcrumbs. The following set of Euclidean distances are computed: Source robot to the first breadcrumb, all adjacent breadcrumbs in the route, the last breadcrumb to the destination robot. From all these distances, we take the largest distance as the range cost. Additionally, there's a distance penalty applied for every breadcrumb present in the route.