Study Group Mathematics with Industry

ESA@day1

Develop a Smart Positioning Algorithms for Indoor Satellite Navigation





ESA

The European Space Agency (ESA) is responsible for the construction of the Galileo system, an augmentation-system for GPS. Satellite Navigation. Satellite navigation has many applications, including route guidance for cars, the navigation of boats and airplanes, and the synchronization of telecom networks. It is has one serious weakness though, it cannot be used inside buildings because interiorly the signal is just too weak. The goal of the workshop project is to extend navigation to the interiors of buildings by using the knowledge of the position of users with respect to each other.

Workshop

Today all problems of the workshop were presented in the plenary session. The whole group also had the chance to get to know each other over lunch. Before lunch, Jaron Samson presented the problem of ESA: navigation inside buildings and how GPS and the European Galileo satellite system can still help with that. He explained his approach of letting users determine their relative distances to a few neighbors and fixed wireless routers. Given the absolute position of a few users outside the building this then determines the absolute position of each user in the network.

After Lunch we had second round of presentations, and people selected their favourite problem. The afternoon ended with some further explanation by Jaron. He once again explained the model. Abstractly the model is about

1. GPS devices which can

a. determine their absolute position with high precision in the reference frame of the earth, corresponding to users on parking lots and near windows.

b. Exchange information

2. Devices which can

a. determine the relative distances with each other and GPS devices, with typically rather lower precission

b. exchange some information.

3. Devices of type 2 (base stations) which are fixed with respect to the building.




This quickly led to some discussion on the technical feasibility of the abstracted version of the in building navigation problem, because in reality mobile devices, other than gps, are not actually very well suited to determine distances. We agreed however, (after some discussions which let Jaron to get some suspiciously foamy and yellowish glass of water to sooth his throat J) that this is a matter of technical progress. Indeed pseudolights with groundbased GPS transmitters are used in air and normal ports. It also involves breaking the chicken and egg problem, that there are no such devices and therefore there is no supporting infrastructure like transmitters with a known position and standard methods for getting a map of the building. In any case these problems are outside the skope of the workshop, and as an abstract model this works fine.

The algortithmic problem is now
Given an existing a seed network of size N (which could be just one device, GPS or otherwise)

• Find a probability distribution on (R^2)^N which suitably represents the probability distribution of the position of all the users. If we do not have sufficient information to determine absolute distributions this might well be invariant under a symmetry group of Euclidean motions and therefore NOT localized around a single point (Having one GPS device in the network breaks the symmetry to Orthogonal group O(2), tor the Z/2Z reflections in the line through the devices, no GPS devices mean that the symmetry group is non compact which is not nice, so it is probably best to assume at least one GPS node).

• Given probability distributions of the distances of a new node to M neighbors
  
• Broadcast information of this new node distribution to M’ neighbors.
• Let those M’ neighbors update their probability distributions
• Broadcast again…
• repeat
• Determine convergence, and if possible prove optimality of convergence rates