Locating UAV's using ground stations

By Arryon Tijsma and Noel Luneburg

Project for the A.I. course Multi-Agent Systems 2014-2015

Introduction

By using cheap and small drones for exploration one has the option to combine multiple drones which can cooperate by communicating to execute certain tasks as a group. Drones normally require high-detail wireless connections to transmit data, however, these connections have a limited range. We propose the use of ground stations distributed in a field to serve as landmark guides and data recipients for the drones. Communication between all ground stations will link the entire system together, creating a decentralised or distributed knowledge system. We have developed an application that simulates a field containing drones and ground stations in order to research the acquisition and sharing of knowledge.


Explanation of the system

The goal of the program is to locate all drones in order for a task planner (not part of the application) to plan a new global task, taking into account every drone location. This requires a definition of drones being lost and drones with a known location. We say a drone is lost whenever it is positioned outside of the range of every ground station. Whenever it is hovering stationary within the range of a station, the corresponding station knows the location of that drone. In a real environment this could for instance be achieved using a GPS module on a drone that transmits its position to the station when in range.

Each drone starts by hovering in a stationary position, which either falls outside or inside some station's range. When a drone is located inside a station's range, that station immediately connects to the drone and will then communicate to the other stations that it knows the position of that drone. Communication between stations takes some time which means that whenever a drone reaches a station it will take a little while before every other station is aware of this.

Some drones will not initially be positioned inside any station's range and thus they need to be guided to one of the stations. This is done through a station's ability to send out "satellite" drones. A drone with a know location will be sent away from the station to scout for lost drones. Whenever such a satellite drone gets close enough to such a drone the satellite will tell the drone from which station it came from and how to get there. The lost drone will then follow that direction until it arrives at the station. Whenever a satellite drone has flown for too long it will lose track of the path from its current position to its associated station and will now be lost.


Multi-Agent Systems logic

Initially, each agent (ground station) knows nothing. We generate Kripke worlds for each possible combination of drones connected with ground stations. Those worlds can have formulas, which take the form of our drones. The truth value of a formula is whether or not we know where that drone is.

Kripke worlds relate to the uncertainty for agents in an environment, and all the possible options available. When starting the simulation, nothing is known about the positions of the drones, so all possible Kripke worlds adhering to our restrictions (only one associated ground station per drone) are possible for all stations. If there is only one Kripke world possible for all agents, that means there is no uncertainty, which is what we strive for.

For each agent, the possible Kripke worlds can be reduced by gaining knowledge, and increased by losing knowledge. Say we have two drones and two stations, and we connect one drone to station 1. The Kripke world where station 1 has a local state of zero has become impossible, so we've reduced the number of Kripke worlds. Conversely, if the drone gets disconnected from the station, that world has become possible again.

At each point in time, we can show for which drones the location is known. We say 'Everybody knows where drone X is' if all ground stations know this, in all accessible Kripke worlds. We say it is implicit that we know where drone X is, if at least one ground station knows this


Results

We have run simulations to determine the behavior of the drones using the provided heuristics and to determine how fast the number of Kripke worlds converges to one, until all drone positions are known. Since there is probability involved we ran the simulation fifteen times for each of the combinations of drones versus ground stations.

Generation of the cartesian product for the initial Kripke worlds is a consuming task that grows exponentially with the number of ground stations added. Therefore, combinations of many drones and many ground stations are not suitable for our simulation.

The possible Kripke worlds grow exponentially at higher values of drones x stations. It shows that with more ground stations, drones are discovered more easily, which is logical. It also shows that if more drones are present in the same area, they are located faster, probably because the chances another drone will get in their vicinity is larger.

You can read the report (linked at the top of the page) for the full results of the simulation

Conclusions

Our research question was: how to describe topological/spatial knowledge within a decentralised network of agents using migrating drones as sensors?

As an answer to this question, the simulation proves quite useful. It seems with the correct strategy, it is fairly simple to simulate a situation where drones will gravitate towards various ground stations until their position is known and communicated between all ground stations. Using more drones will not guarantee a faster convergence to full knowledge but adding more stations will significantly speed up the process. The reason behind this is quite simple: The drones will have less space where they can be lost as more ground station will cover more areas in which locations of drones are known.

Running the simulation

For the simulation, pygame and numpy need to be installed on the system. On linux, this can be achieved with apt-get install python-pygame python-numpy

To run the simulation, unzip the application and navigate to the folder in a terminal, then type python drone_simulation.py

Input how many drones the simulation should run, and how many stations. Be careful of configurations above 30-3, since that will make generating all possible Kripke worlds exponentially slow