Robot-robot team: cooperative games

With the recent advances in technology, there are many cases where teams of robots should coordinate in order to achieve a common goal. This includes the classic control aspect of moving the robots from point A to point B. But there should be also another part that will act as a coordination mechanism between the robots, in order to take into account what other robots are doing and how the actions of the other robots influences the whole team outcome. Game theory provides a mathematical framework in order to achieve this. The simplest game is matching pennies.

You have two players, so two persons have a penny in their hand - which is 20p actually - and they have to place the coin on the table. If the faces of the coins are the same, then one player wins. If it’s not the same, then the other player wins. The simple matching pennies game can be transformed slightly and work as a collision avoidance mechanism between UAVs. So now, consider the matching pennies game where two players place a coin on the table, but both of them win if they choose different faces, and both of them lose if they choose exactly the same face of the coin.

So, consider two UAVs that are flying in opposite directions, and they will collide if they keep going to their target. And they have two altitudes to fly, or a high altitude and low altitude. This gives us a game, like the one that we described before. If they each choose the same action, both of them try to fly the low or high altitude, then they cannot accomplish their mission, and they lose at the game. But if they choose to fly at different altitudes, so one of the coins is heads, the other is tails, then they can accomplish their mission and pass with one on top of the other.

We have a framework of how we can describe the process of choosing an altitude by game theory, by how the robots decide which altitudes they will fly. And the answer to this can come from game theoretic learning. This is usually an iterative process where two players, or in our case the two UAVs, are flying and change altitudes. Then they learn what the other UAV is doing, and eventually, they choose different altitudes to fly.