Naar de content

Orde in luchtkaarten

Informaticus neemt luchtverkeersleiding werk uit handen

Wikimedia Commons

Een Nederlandse informaticus heeft een computerprogramma gemaakt om labels op kaarten of radarbeelden te laten bewegen. Dat kan zorgen voor een betere luchtverkeersleiding en uitgebreidere kaarten op je GPS.

Een air traffic controller heeft een stressvolle baan. Constant het luchtruim in de gaten houden terwijl je piloten vertelt waar en hoe ze moeten landen – ga er maar eens aan staan. Zou het dan ook niet mooi zijn als één deel van het werk voortaan eenvoudiger kan? Dat dacht Dirk Gerrits van de TU Eindhoven ook.

Luchtverkeersleiders aan het werk, op een vliegbasis in de VS

Wikimedia Commons

Hij promoveerde als informaticus onlangs onder andere op een probleem van luchtverkeersleiders: het labelen van vliegtuigen. Op het scherm van een verkeersleider zijn op elk moment veel vliegtuigen te zien. Ze hebben allemaal een label met informatie. Vluchtnummer, snelheid, hoogte, enzovoort. Maar als het druk wordt in het luchtruim, komt het regelmatig voor dat de teksten van twee of meer vliegtuigen overlappen.

Dan moet de luchtverkeersleider met de hand het label ergens anders heenslepen – weer een handeling in zijn toch al drukke werk. Gerrits raakte geïnspireerd toen hij het nationaal lucht- en ruimtevaarttechniek-laboratorium bezocht. Daar hoorde hij over het labelprobleem. “Ik vond het belachelijk dat dat met de hand moest. Dus heb ik geprobeerd om het labelproces dynamisch te maken. Dan past het zich aan aan de positie van het vliegtuig, en de posities van andere vliegtuigen. Het was echter niet gemakkelijk.”

Geen ideale manier

Het probleem is dat er geen optimale labelmethode is, die de labels in een relatief korte rekentijd kan plaatsen. “We wisten al dat het probleem voor stilstaande punten zo lastig was; het is een NP-moeilijk vraagstuk. Ik ontdekte dat het probleem voor bewegende labels nóg lastiger is, namelijk PSPACE-moeilijk. Dat is een soort nog moeilijker vorm van NP-moeilijke problemen.” Die laatste categorie is bekend, en omvat een heleboel wiskundeproblemen (waaronder het handelreizigersprobleem).

PSPACE-moeilijk gaat een stapje verder. Het best legt Gerrits het uit met een voorbeeld: “Een NP-moeilijk probleem is het spel TipOver : een eenpersoonsspelletje met de vraag: kan ik een reeks zetten doen zó dat ik mijn doel bereik (en het spelletje win)? Een PSPACE-moeilijk probleem is een tweepersoonsspel, zoals Othello (ook wel bekend als Reversi). Daarbij is de vraag: kan ik een zet doen zó, dat ik na de beurt van mijn tegenstander weer een zet kan doen, enzovoort, tot ik uiteindelijk met zekerheid win? PSPACE-moeilijke problemen hebben dus een hele extra laag complexiteit in de vorm van een ‘tweede speler’.”

Dat was een tegenslag; het betekent dat er geen perfecte oplossing voor het labelprobleem was. Gelukkig is er in de praktijk vaak een benadering van een perfecte oplossing te vinden. “Ik heb met mijn methode toch behoorlijk wat bereikt.”

Elk vliegtuig een label

In het programma heeft élk vliegtuig een label (een eis bij deze versie van het probleem; er mogen geen ongelabelde vliegtuigen op het scherm staan), en overlappen de labels maar heel zelden. Verder kan je daar een beetje mee schuiven. “Als je de labels heel secuur wilt plaatsen, vrijwel zonder overlap, dan ontstaat een nieuw probleem. Daardoor verschieten de labels namelijk, en dat trekt de aandacht van je oog. Ik wil het liefst zorgen dat alles er smooth uitziet, dus moet je een beetje meer overlap op de koop toe nemen.”

Niet alleen luchtverkeersleiders kunnen baat hebben bij Gerrits’ werk. Ook navigatiefabrikanten – en andere makers van digitale kaarten – kunnen er wat mee. “Ook bij kaarten zijn labels belangrijk. En op de display van een GPS verandert het beeld constant, dus ook de locatie van de labels. Op dit moment gaat dat ook vaak mis, zeker in drukke gebieden.”

De aanpak is daarbij wel anders. Bij luchtverkeersleiding moet elk vliegtuig een label hebben, en wil je zo min mogelijk overlap. Bij kaarten is het minder belangrijk dat alles een label heeft, en daardoor kan je minder overlap bewerkstelligen. Sterker nog: het is onmogelijk om op een stilstaande kaart alles te labelen. Daarom moet een kaartlabelalgoritme dus veel meer aandacht besteden aan wát te labelen; welke bezienswaardigheden in een stad zijn belangrijk, of, bij een wereldkaart, welke steden zijn belangrijk? Op dat gebied is al veel onderzoek gedaan.

Stellingen
Gerrits herstelt een oude, Hollandse universiteitstraditie in eer: de stellingen. Aan het einde van zijn proefschrift vind je een lijst van wetenschappelijke, maatschappelijke en humoristische stellingen. ‘Ik wil laten zien dat je als wetenschapper meer bent dan alleen maar een rekenaar in een lab. We horen bij de maatschappij, zijn er onderdeel van. Dat wilde ik graag laten zien en zo’n promotie is er een uitgelezen moment voor. De traditie van stellingen verdwijnt, en dat vind ik jammer.’ Een selectie van stellingen:
  • De Nederlandse verdeling van onderzoeksgeld is homeopathisch: de overheid denkt dat meer en meer verdunnen beter en beter onderzoek voortbrengt.
  • Open acces, het gratis toegankelijk maken van wetenschappelijke artikelen, had jaren geleden al standaard moeten zijn.
  • ‘het is makkelijk om te zien dat…’ is een geweldige zin: je geeft toe dat je zelf niet het antwoord kon vinden, maar de lezer voelt zich dom.

Ondertussen wordt het algoritme nog niet toegepast door luchtverkeersleiders. “Het is nog de vraag of er ook echt tests komen, waarbij een verkeersleider met mijn labelprogramma vliegtuigen laat landen. Ik hoop van wel, maar ben ondertussen ook alweer met een heel ander onderwerp bezig. Bovendien is de luchtvaartwereld redelijk conservatief: if it ain’t broke, don’t fix it. Zo zijn ze relatief recent pas op kleurendisplays overgestapt. Het is ook begrijpelijk; je moet zeker weten dat een nieuwe techniek altijd werkt en 100 procent betrouwbaar is. Dat maakt het accepteren van nieuwe techniek lastig, ook al werkt het beter dan wat je nu gebruikt.”

Gerrits’ nieuwe methode zou ook voor taxicentrales of transportbedrijven nuttig zijn. De baas zou dan in één oogopslag kunnen zien waar zijn taxi’s of vrachtwagens zijn, zonder afgeleid te worden door allerlei onnodige informatie. Op dit moment bestaan zulke geavanceerde digitale kaarten nog niet.

Bron

Pushing and Pulling: Computing push plans for disk-shaped robots, and dynamic labelings for moving points, Dirk Gerrits, Promotor: prof.dr. M. de Berg (TU/e);
Co-promotor: dr. K. Buchin (TU/e), Technische Universiteit Eindhoven, 22 August, 2013, 16:00