Greedy-Face-Greedy: Bridging the Gap in Decentralized Human Tracking

TL;DR

Locating friends in crowded, indoor environments like malls or campuses often fails due to poor GPS/Wi-Fi signals. This paper presents an optimized version of the Escort system, utilizing a Greedy-Face-Greedy (GFG) routing algorithm and a strategic "seeker" node to slash tracking path lengths by 42% while ensuring efficient, infrastructure-free navigation.

Academic Context: This work functions as a performance optimization for opportunistic localization systems, shifting from purely trace-based routing to a path-integrated geographic model.

Problem & Motivation: The "Long Way Around" Dilemma

The original Escort system was a breakthrough because it allowed user A to find user B using only accelerometers, compasses, and audio-based encounters—no GPS required. However, it suffered from two critical flaws:

1. Inefficient Paths: Directions were based on where people had already walked. If two people were separated by a wall but their trails only met 500 meters away at an entrance, the system would send them on that 500m detour.
2. Computational Bottlenecks: Using the Floyd-Warshall algorithm to compute shortest paths on a constantly growing trail graph scales poorly ($O(n^3)$), making it unsuitable for large-scale mobile social networks.

The author's insight: If we can introduce a "seeker" who knows the map and can proactively find shortcuts between trail intersections using geographic routing, we can "stitch" the fragmented trail graph into a much more efficient network.

Methodology: The GFG Integration

The core of the solution is the Greedy-Face-Greedy (GFG) algorithm, a classic in geographic routing known for its guaranteed delivery in planar graphs.

1. The Seeker Node

Unlike standard users, the Seeker possesses a digital map of the area. As the seeker moves, it identifies better paths between known junctions using GFG logic. These "optimized segments" are then uploaded to the Escort server.

2. GFG Routing Mechanics

• Greedy Mode: The system always tries to move to the neighbor closest to the target destination.
• Face Mode: If a "local minimum" is reached (no neighbors are closer than the current node), the system switches to Face routing, traversing the perimeter of the graph's faces until greedy progress can resume.

Fig 1: Example of the tracking problem where the original trail (yellow) is significantly longer than the map-aware path (black).

3. Graph Merging

The server merges these GFG-discovered paths into the existing trail graph. When a user requests a route, the server calculates two options: the encounter-based trail and the GFG-assisted trail, selecting the shorter of the two.

Experiments & Results: Efficiency Gains

The researchers simulated the environment using the Temple University campus as a backdrop, varying user counts from 8 to 20.

Key Findings:

• Path Reduction: The GFG-assisted paths were roughly 42% shorter than the original Escort paths.
• Proximity to Optimal: The proposed method reached within 20% of the theoretical shortest path (Dijkstra on a full map), a remarkable achievement for a system that doesn't require a global GPS lock for every user.
• Scalability: By utilizing local geographic information, the complexity for calculating paths was reduced to $O(N^2)$ for the entire network.

Fig 2: Performance comparison showing GFG-assisted routing (middle bars) consistently outperforming the original Escort traces.

Critical Analysis & Conclusion

Takeaway

The integration of GFG routing proves that opportunistic social data (who met whom and where) is most powerful when anchored by topological knowledge (the map). By adding just one map-aware "seeker," the utility of the entire decentralized network increases exponentially.

Limitations

• Seeker Dependency: The system's performance gain is heavily dependent on the seeker's movement. If the seeker doesn't cover high-traffic shortcuts, the efficiency drops back to baseline.
• Planar Graph Assumption: GFG routing assumes a planar graph; complex multi-level indoor structures (like mezzanines) might require 3D-aware variants of the algorithm.

Future Outlook

This approach paves the way for "Crowdsourced Mapping," where users don't just find each other, but collectively build and optimize a navigation layer for indoor spaces where traditionally dominant technologies like Google Maps often fail to provide granular accuracy.