Path­fin­ding: Weg­fin­dung in der In­for­ma­tik

Path­fin­ding-Al­go­rith­men gehören zu den be­kann­tes­ten und am häu­figs­ten zum Einsatz kommenden Al­go­rith­men. Wir zeigen, wie Path­fin­ding funk­tio­niert und wofür es ein­ge­setzt wird.

Was ist Path­fin­ding?

Path­fin­ding, auch bekannt als Weg­fin­dung, ist ein grund­le­gen­des Problem in der In­for­ma­tik. Beim Path­fin­ding geht es darum, den kürzesten oder ef­fi­zi­en­tes­ten Weg zwischen zwei Punkten zu finden. Es gibt eine Vielzahl an Path­fin­ding-Al­go­rith­men, die in ver­schie­de­nen An­wen­dungs­sze­na­ri­en zum Einsatz kommen.

Wie funk­tio­niert Path­fin­ding und wofür wird es ein­ge­setzt?

Ein Path­fin­ding-Al­go­rith­mus beginnt in der Regel damit, das Problem als Graph oder Gitter dar­zu­stel­len. Ein Graph ist eine Sammlung von Knoten, die durch Kanten verbunden sind; bei­spiels­hal­ber stelle man sich ein Fluss­dia­gramm vor. Bei einem Gitter handelt es sich um ein zwei­di­men­sio­na­les Feld von Zellen, wie ein Schach­brett. Die Knoten oder Zellen re­prä­sen­tie­ren Standorte im Pro­blem­raum, während die Kanten oder be­nach­bar­te Zellen die möglichen Wege da­zwi­schen dar­stel­len.

Sobald das Problem als Graph oder Gitter dar­ge­stellt ist, verwenden Path­fin­ding-Al­go­rith­men ver­schie­de­ne Techniken, um den Weg zwischen zwei Punkten zu finden. Für ge­wöhn­lich zielen die Al­go­rith­men darauf ab, den kürzesten oder güns­tigs­ten Weg zu finden und dabei so effizient wie möglich vor­zu­ge­hen.

Close

Path­fin­ding-Al­go­rith­men haben viele An­wen­dun­gen in der In­for­ma­tik, darunter:

• Robotik: Path­fin­ding-Al­go­rith­men werden verwendet, um autonome Roboter bei der Na­vi­ga­ti­on durch komplexe Um­ge­bun­gen zu un­ter­stüt­zen. Man denke an selbst­fah­ren­de Autos oder smarte Staub­sauger, die das Eigenheim selbst­tä­tig durch­fah­ren.
• Vi­deo­spie­le: In Vi­deo­spie­len werden Path­fin­ding-Al­go­rith­men verwendet, um die Be­we­gun­gen von Nicht-Spieler-Cha­rak­te­ren (NPCs) zu steuern. Sendet man in einem Echtzeit-Stra­te­gie­spiel Einheiten per Klick in die geg­ne­ri­sche Basis, kommen ebenfalls Path­fin­ding-Al­go­rith­men zum Einsatz.
• Logistik: Path­fin­ding-Al­go­rith­men kommen in der Logistik zum Einsatz, um den ef­fi­zi­en­tes­ten Weg für den Transport von Waren oder Personen zu finden.
• Ver­kehrs­pla­nung: Path­fin­ding-Al­go­rith­men werden verwendet, um die besten Wege für den Verkehr einer Stadt zu planen und dabei Staus zu vermeiden.
• Netzwerk-Routing: In Com­pu­ter­netz­wer­ken werden Path­fin­ding-Al­go­rith­men verwendet, um den schnells­ten Weg für die Da­ten­über­tra­gung zwischen ver­schie­de­nen Netz­werk­kno­ten zu finden.

Schauen wir uns einige An­wen­dungs­mög­lich­kei­ten von Path­fin­ding im Detail an.

Path­fin­ding in der Logistik

Beim Path­fin­ding in der Logistik geht darum, die beste Route für den Transport von Gütern zu finden. Eine optimale Route minimiert Kosten und Reisezeit und ge­währ­leis­tet gleich­zei­tig die Si­cher­heit der trans­por­tier­ten Produkte. Damit ist Path­fin­ding in der Logistik ein ent­schei­den­des Werkzeug zur Op­ti­mie­rung der Bewegung von Gütern und zur Kos­ten­re­du­zie­rung.

Ver­an­schau­li­chen wir uns an einer Handvoll Beispiele, wie in der Logistik Path­fin­ding ein­ge­setzt wird:

• Fahr­zeug­rou­ting: Bei der Gü­ter­be­för­de­rung op­ti­mie­ren Path­fin­ding-Al­go­rith­men die Route von Lie­fer­fahr­zeu­gen. Der Al­go­rith­mus be­rück­sich­tigt Faktoren wie Ent­fer­nung, Ver­kehrs­be­din­gun­gen und Lie­fer­zeit­be­schrän­kun­gen, um die ef­fi­zi­en­tes­te Route zu erstellen.
• Be­stands­ma­nage­ment: Path­fin­ding wird im Be­stands­ma­nage­ment bzw. der La­ger­ver­wal­tung verwendet, um die Plat­zie­rung von Gütern zu op­ti­mie­ren. Dies stellt sicher, dass die Güter an den jeweils optimalen Po­si­tio­nen gelagert werden. So werden Aufwand und Zeit beim Abruf und der Aus­lie­fe­rung der Güter reduziert.
• Supply-Chain-Ma­nage­ment: Path­fin­ding-Al­go­rith­men kommen zum Einsatz, um die gesamte Lie­fer­ket­te von ihrem Ursprung bis zur Aus­lie­fe­rung zu op­ti­mie­ren. So wird si­cher­ge­stellt, dass die Produkte möglichst effizient und kos­ten­güns­tig trans­por­tiert werden.

Path­fin­ding in Vi­deo­spie­len

Path­fin­ding in Vi­deo­spie­len ist ein wichtiges Werkzeug zur Er­schaf­fung von ein­drucks­vol­len und rea­lis­ti­schen Spiel­wel­ten. Die Technik erlaubt Einheiten und Nicht-Spieler-Cha­rak­te­ren („Non-player cha­rac­ters“, NPCs), sich in der Spielwelt rea­lis­tisch und effizient zu bewegen. Dabei werden Path­fin­ding-Al­go­rith­men verwendet, um den optimalen Pfad für die Bewegung von NPCs zu bestimmen und dabei Hin­der­nis­se und andere Gefahren zu vermeiden.

In Vi­deo­spie­len kommt Path­fin­ding u. a. für die folgenden Aufgaben zum Einsatz:

• Feind­li­che NPCs: Path­fin­ding wird ein­ge­setzt, um das Verhalten von feind­li­chen NPCs zu steuern. So können NPCs den Spieler verfolgen und dabei Hin­der­nis­sen und anderen Gefahren aus­wei­chen.
• Einheiten-Steuerung: Per Path­fin­ding wird die Bewegung von freund­li­chen Einheiten in der Spielwelt gesteuert. Dies kann das Führen von NPCs zu ihrem Ziel oder das Folgen des Spie­ler­cha­rak­ters umfassen.
• Hin­der­nis­ver­mei­dung: Path­fin­ding-Al­go­rith­men stellen sicher, dass Einheiten Hin­der­nis­sen wie Wänden, Klippen oder anderen Gefahren aus­wei­chen.
• Karten- / Le­vel­ge­nerie­rung: Auch zur pro­ze­du­ra­len Ge­ne­rie­rung von Karten oder Leveln kommen Path­fin­ding-Al­go­rith­men zum Einsatz. Dies er­mög­licht die Er­stel­lung rea­lis­ti­scher und ab­wechs­lungs­rei­cher Spiel­wel­ten.

Path­fin­ding beim Netzwerk-Routing

Path­fin­ding kommt beim Netzwerk-Routing zum Einsatz, um optimale Wege für Da­ten­pa­ke­te durch ein Netzwerk zu finden. Path­fin­ding-Al­go­rith­men bieten Netz­werk­ad­mi­nis­tra­to­ren die Mög­lich­keit, angepasst an die je­wei­li­gen Ge­ge­ben­hei­ten die Netz­werk­per­for­mance zu ver­bes­sern. Zu den gängigen An­wen­dungs­mög­lich­kei­ten des Path­fin­ding im Netzwerk-Routing gehören:

• Traffic En­gi­nee­ring: Path­fin­ding-Al­go­rith­men helfen, den Netz­werk­ver­kehr zu op­ti­mie­ren und Über­las­tung zu mi­ni­mie­ren. Durch Analyse der Netz­werk­to­po­lo­gie und der Ver­kehrs­mus­ter lassen sich mit Path­fin­ding-Al­go­rith­men die ef­fi­zi­en­tes­ten Pfade für Da­ten­pa­ke­te durch das Netzwerk iden­ti­fi­zie­ren.
• Quality of Service (QoS): Mithilfe von Path­fin­ding-Al­go­rith­men lässt sich der Netz­werk­ver­kehr basierend auf QoS-An­for­de­run­gen prio­ri­sie­ren. Bei­spiels­wei­se werden zeit­kri­ti­sche Daten wie VoIP oder Vi­deo­streams prä­fe­riert durch das Netzwerk geroutet. Dabei kommt die Prio­ri­sie­rung als Teil der Kos­ten­funk­ti­on zum Einsatz.
• Las­ten­aus­gleich: Speziell an­ge­pass­te Path­fin­ding-Al­go­rith­men werden verwendet, um den Netz­werk­ver­kehr auf mehrere Pfade zu verteilen. Durch die Las­ten­ver­tei­lung helfen Path­fin­ding-Al­go­rith­men, die Netz­werk­per­for­mance zu ver­bes­sern und das Risiko von Über­las­tun­gen zu re­du­zie­ren.
• Aus­fall­si­cher­heit: Path­fin­ding-Al­go­rith­men kommen zum Einsatz, um im Fall von Netz­werk­aus­fäl­len al­ter­na­ti­ve Pfade für den Da­ten­fluss zu finden. So wird si­cher­ge­stellt, dass Da­ten­pa­ke­te zu­ver­läs­sig zu­ge­stellt werden, wenn eine Netz­werk­kom­po­nen­te ausfällt.

Path­fin­ding in der Ver­kehrs­pla­nung

Path­fin­ding wird im Ver­kehrs­we­sen verwendet, um den Ver­kehrs­fluss zu op­ti­mie­ren und Staus zu re­du­zie­ren. Path­fin­ding-Al­go­rith­men helfen Ver­kehrs­in­ge­nieu­ren und -in­ge­nieu­rin­nen, ef­fi­zi­en­te Ver­kehrs­net­ze zu entwerfen und Stra­te­gien zur Ver­bes­se­rung des Ver­kehrs­flus­ses zu ent­wi­ckeln. Einige der wich­tigs­ten An­wen­dun­gen von Path­fin­ding im Ver­kehrs­we­sen sind:

• Rou­ten­pla­nung: Path­fin­ding-Al­go­rith­men kommen zum Einsatz, um optimale Routen für Fahrzeuge zu planen und dabei über­las­te­te Bereiche zu vermeiden. So lassen sich der Ver­kehrs­fluss ver­bes­sern und Ver­zö­ge­run­gen re­du­zie­ren.
• Ver­kehrs­am­pel-Op­ti­mie­rung: Path­fin­ding-Al­go­rith­men können ein­ge­setzt werden, um die Schaltung von Ver­kehrs­am­peln basierend auf Ver­kehrs­mus­tern und Ver­kehrs­nach­fra­ge zu op­ti­mie­ren. Die Syn­chro­ni­sie­rung von Ver­kehrs­am­peln und die Anpassung von Zeit­plä­nen kann den Ver­kehrs­fluss ver­bes­sern.
• Er­eig­nis­ma­nage­ment: Path­fin­ding-Al­go­rith­men werden ein­ge­setzt, um al­ter­na­ti­ve Routen für Fahrzeuge im Fall von Unfällen oder Stra­ßen­sper­run­gen zu iden­ti­fi­zie­ren. So hilft das Path­fin­ding, Staus zu re­du­zie­ren und den Ver­kehrs­fluss in be­trof­fe­nen Bereichen zu ver­bes­sern.
• Öf­fent­li­cher Verkehr: Mittels Path­fin­ding-Al­go­rith­men lassen sich öf­fent­li­che Ver­kehrs­we­ge und Fahrpläne op­ti­mie­ren. Dies trägt dazu bei, die Effizienz von öf­fent­li­chen Ver­kehrs­sys­te­men zu ver­bes­sern und Ver­kehrs­über­las­tun­gen zu re­du­zie­ren.

Welche Path­fin­ding-Al­go­rith­men gibt es?

Die Her­aus­for­de­run­gen beim Path­fin­ding ergeben sich aus den Ein­schrän­kun­gen des spe­zi­fi­schen Pro­blem­raums. So müssen Hin­der­nis­se, die den direkten Weg ver­sper­ren, mit­be­dacht werden, genauso wie etwaige Kosten für die Fort­be­we­gung im Raum. Dabei können die Kosten mul­ti­di­men­sio­nal sein, z. B. wenn ein Weg zwar en­er­ge­tisch günstiger, dafür jedoch mit einer längeren Reisezeit belegt ist.

Ggf. müssen fest­ge­leg­te Punkte in den Weg mit­auf­ge­nom­men werden; dabei stellt ein Path­fin­ding-Al­go­rith­mus sicher, dass bei der Bewegung im Raum nicht im Kreis gelaufen wird. Generell muss ein optimaler Weg möglichst effizient gefunden werden, vor allem, wenn die Weg­fin­dung in Echtzeit statt­fin­den soll.

Einige gängige Path­fin­ding-Al­go­rith­men sind:

• Breadth-First Search (BFS): Dieser Al­go­rith­mus erkundet alle be­nach­bar­ten Knoten des Start­punkts, bevor er zur nächsten Ebene von Knoten übergeht, bis das Ziel erreicht ist.
• Dijkstra-Al­go­rith­mus: Dieser Al­go­rith­mus erkundet den Graphen, indem er zuerst einen dem Start­punkt nächst­ge­le­ge­nen, un­er­forsch­ten Knoten besucht und dann iterativ die Ent­fer­nung aller Knoten vom Start­punkt ak­tua­li­siert, bis das Ziel erreicht ist.
• A*-Suche: Dieser Al­go­rith­mus kom­bi­niert die Ideen von BFS und Dijkstra-Al­go­rith­mus, indem er eine heu­ris­ti­sche Funktion verwendet, um die Suche zum Ziel­kno­ten zu führen.
• Gierige Best-First-Suche: Dieser Al­go­rith­mus wählt den nächsten zu er­kun­den­den Knoten aus, basierend auf einer heu­ris­ti­schen Schätzung der Ent­fer­nung zum Ziel­kno­ten.
• Bi­di­rek­tio­na­le Suche: Dieser Al­go­rith­mus sucht gleich­zei­tig vom Start- und Ziel­kno­ten aus zur Mitte des Graphen, um den kürzesten Weg zu finden.