Karta i cilj su poznati; traži se put. Zvuči jednostavno, ali izbor načina na koji se prostor prikaže odlučuje hoće li se put naći u milisekundi ili u minuti — i koliko će biti dug.
Planiranje putanje uzima tri stvari: kartu sa proširenim zaprekama iz jedinice 3.3, trenutačni položaj iz modula 5 i cilj. Daje jednu stvar: niz točaka od prvoga do drugoga kroz koje vozilo može proći.
Ono što planiranje ne radi jednako je važno. Ne prati vozilo u vožnji, ne reagira na ono što se pojavi, ne zadaje brzine kotača. To su poslovi drugih dviju jedinica ovoga modula. Planiranje se izvede jednom — ili nekoliko puta u sekundi, ovisno o izvedbi — i preda put dalje.
Ključna odluka nije koji postupak nego kako prikazati prostor. Traženje puta u neprekidnoj ravnini nije izvedivo, jer položaja ima beskonačno mnogo. Prostor se zato svede na konačan broj mjesta i veza — na graf — i tek se u njemu traži put. Različiti načini tvorbe grafa daju različite putanje, i o tome je ova jedinica.
Prohodan je prvi i neizostavan — ne smije dodirivati proširene zapreke. Kratak je drugi, ali ne po svaku cijenu: put koji je dva metra kraći, a prolazi na deset centimetara od police, lošiji je od duljega kroz sredinu hodnika. Izvediv je treći: vozilo koje se ne okreće u mjestu ne može izvesti put s oštrim kutom, koliko god on bio kratak. I gladak je četvrti, jer svaki lom putanje znači kočenje i ubrzanje.
Iz iste karte mogu se napraviti dva vrlo različita grafa, i oni daju različite putanje.
Mreža uzima kvadratiće karte kao čvorove, a susjedstvo kao veze. Svaki je kvadratić spojen sa svojim susjedima — četirima ako se dopušta samo vodoravno i okomito, ili osam ako se dopušta i dijagonalno.
Graf vidljivosti uzima samo uglove zapreka kao čvorove, a vezu postavlja između svakoga para uglova koji se međusobno vide — to jest između kojih se može povući ravna crta koja ne siječe nijednu zapreku.
Odaberi prikaz i usporedi.
Razlika u duljini nije mala. Mreža sa četirima susjedima daje put koji se penje stubama i može biti do 41 posto dulji od ravne crte; s osam susjeda pada na oko 8 posto. Graf vidljivosti daje doista najkraći put, jer se sastoji od ravnih dionica između uglova.
Ali graf vidljivosti ima ozbiljnu manu: put mu ide točno uz uglove zapreka. To je najkraće i najopasnije. U praksi se zato ili zapreke šire i za sigurnosni razmak, ili se putanja naknadno zaobli i odmakne od uglova.
Kad je graf napravljen, traženje puta je stara i dobro riješena zadaća. Postupak je uvijek isti: od polazišta se šire mjesta koja su već dosegnuta, i za svako se pamti koliko je do njega najjeftinije doći i odakle se došlo. Kad se dosegne cilj, put se pročita unatrag.
Razlika među postupcima je samo u tome kojim redom se mjesta obrađuju.
| Postupak | Bira sljedeće mjesto po | Nalazi najkraći put | Koliko obiđe |
|---|---|---|---|
| Pretraživanje u širinu | broju koraka od polazišta | da, ako su svi koraci jednako skupi | mnogo — širi se na sve strane jednako |
| Pretraživanje po cijeni | prijeđenome putu od polazišta | da, i uz različite cijene koraka | mnogo — i dalje se širi u krug |
| Pohlepno prema cilju | procijenjenoj udaljenosti do cilja | ne | malo, ali zna zaglaviti iza zapreke |
| Pretraživanje s procjenom | zbroju prijeđenoga puta i procjene ostatka | da, ako procjena nikad ne pretjera | znatno manje od prvih dvaju |
Posljednji redak je onaj koji se u praksi koristi. Ideja mu je jednostavna: umjesto da se širi jednako na sve strane, pretraživanje se nagne prema cilju dodavanjem procjene koliko je ostalo. Kao procjena se uzima ravna udaljenost do cilja — ona nikad ne pretjeruje, jer stvarni put ne može biti kraći od ravne crte, a upravo to jamči da će se naći najkraći put.
f = g + h
Gdje je g stvarni prijeđeni put od polazišta do toga mjesta, a h procjena ostatka do cilja. Uzme li se h = 0, postupak se svede na pretraživanje po cijeni; uzme li se g = 0, na pohlepno traženje. Zbroj daje najbolje od obojega.
Klikni „Pretraži“ i gledaj koliko se mjesta obiđe.
Razlika je u praksi golema. Na karti skladišta s nekoliko stotina tisuća ćelija pretraživanje bez procjene obiđe gotovo cijelu kartu; s procjenom obiđe usku traku prema cilju. Rezultat je isti put, nađen desetak puta brže.
Postoji i posve drukčiji pristup, koji ne gradi graf niti išta pretražuje. Zamisli da cilj privlači vozilo, a svaka zapreka ga odbija, kao istoimeni polovi magneta. Zbroj svih tih sila u svakoj točki daje smjer u kojem se vozilo giba.
F = Fcilj + Σ Fzapreka
Privlačenje raste s udaljenošću od cilja, odbijanje naglo raste kad se zapreci priđe blizu, a izvan zadanoga dometa je nula. Vozilo u svakome koraku ide u smjeru zbroja.
Prednost je u jednostavnosti i brzini: nema pretraživanja, račun je nekoliko zbrajanja, i postupak sam po sebi izbjegava zapreke koje nisu bile u karti — jer odbijanje računa iz trenutačnoga mjerenja, ne iz karte.
Mana je ozbiljna i zove se lokalni minimum. Ako se privlačenje cilja i odbijanje zapreka ponište, zbroj je nula i vozilo stane — iako cilj nije dosegnut i iako put postoji. Klasičan slučaj je udubina u zidu okrenuta prema cilju: vozilo uđe u nju i zaglavi.
Odaberi raspored i pogledaj kamo vozilo ode.
Zbog te mane potencijalna se polja gotovo nikad ne koriste sama za planiranje. Koriste se uz planiranje grafom: graf daje niz međutočaka kroz prostor, a polje vozi između njih i usput zaobilazi ono što se pojavilo. Tako se dobiva jamstvo da će se cilj doseći i brzina reakcije.
Odabir se svodi na nekoliko pitanja, i rijetko kad je jedan postupak odgovor na sva.
Posljednji je stupac najkorisniji trik cijele jedinice. Umjesto da se traži samo najkraći put, svakoj se ćeliji doda trošak koji raste kako se približava zapreci. Planer koji traži najjeftiniji put tada sam odabere sredinu hodnika — bez ijednoga posebnog pravila.
Planiranje uzima kartu, položaj i cilj i daje niz točaka. Prostor se prije toga mora svesti na graf: mreža uzima kvadratiće kao čvorove i daje put do 41 posto dulji od ravnoga (8 posto s dijagonalama), graf vidljivosti uzima uglove zapreka i daje doista najkraći put, ali uz same uglove. Najkraći se put traži širenjem od polazišta, a dodavanjem procjene ostatka do cilja pretraživanje se nagne prema cilju i obiđe mnogo manje mjesta. Potencijalna polja ne pretražuju ništa i brza su, ali zaglave u lokalnome minimumu, pa se koriste uz planiranje, ne umjesto njega.
Plan vrijedi za prostor kakav je bio u trenutku planiranja. Što kad se promijeni, tema je sljedeće jedinice.
Odgovor se zaključava nakon prvoga klika, uz objašnjenje zašto je točan.