Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
Jakmyśląinteligentnemaszyny
ważna,ponieważuchwyciliśmyproblemwkategoriach,naktórychdobrze
znająsiękomputery.Nieradząsobiezluźnymplanowaniemdrogiwzłożo-
nymśrodowisku,aleakuratwminimalizacjifunkcjisąniezłe.Konceptten
będziecojakiśczaspowracałwniniejszejksiążce.
Wrajdzie,wktórymwziąłudziałHumvee,liczyłsięczas,takwięcRedTeam
przypisałkażdejkomórcemapyowymiarachmetrnametrokreślonywsze-
ściostopniowejskalikoszt,któryodzwierciedlałspodziewanyczas,jakizajmie
pojazdowiprzejechaniebezpieczniejednegometra.Trudnyterenuplasował
sięwyżejnaskalikosztuniżterenłatwy,ponieważpotympierwszymHumvee
musiałbyporuszaćsięwolniej.Zespółprzyznałspecjalnekarytymczęściom
terenu,którebyłynieutwardzone,gdziebrakowałodanychGPS,stromych
inierównych,atakżetymkomórkommapy,któreznajdowałysięzbytdaleko
odkorytarzaokreślonegowspółrzędnymiGPS.Dysponującjużmapązkosz-
temprzypisanymkażdejkwadratowejkomórce,zespółmusiałwyznaczyć
odpowiedniądrogę.
Wprzypadkuznanejmetodywyszukiwaniaścieżkizapomocąalgorytmu
DijkstrykomputerwyszukujeścieżkęprzezpodnoszenieUgranicy”wyszuki-
waniazpunktustartowego
13
.Programwykonujepętlę,przesuwającniecogra-
nicęwrazzkażdymuruchomieniempętli,dopókigranicanieosiągniepunk-
tudocelowego.Wrazzpodnoszeniemgranicyprzezprogrampowolizwiększa
siękoszt,któryprogramskłonnyjestponosićzadotarciedojakiegokolwiek
punktuwramachgranicy;takwięcilekroćrozciągagranicę,zawierającwniej
kolejnypunkt,ównowypunktlokujesięnakrawędzitego,ileprogramjest
skłonnyzapłacić.Zrozciąganiagranicywtakisposóbpłynietakaotokorzyść,
żemożnadziękiniemuprowadzićwyszukiwaniewśródnajbardziejobiecują-
cychtras-takichjakpłaskiedrogi,którymprzypisanyjestniskikoszt-nadłu-
goprzedtem,zanimprzystąpisiędowyszukiwaniawobrębietrudnychtras,
naprzykładtrudnegoterenupozbawionegodróg.
Wmomenciegdyosiągniętyzostaniepunktdocelowy-wprzypadkusa-
mochoduautonomicznegojesttocelpodróży-komputerwiejuż,żeścieżka
istnieje,iznatakżejejkoszt.Oilekomputerprzechowujedanenatematroz-
mieszczeniagranicnamapie,możesprawniecofnąćsięiznaleźćnajkrótszą
ścieżkędopunktudocelowego.Ilustracje2.3a,2.3bi2.3cukazują,jakwygląda
zarównonajkrótszaścieżka,jakigranicawyszukiwania.
Informatycyirobotycypoświęciliwielelatnabadanietegotypualgoryt-
mówiwiedzą,wjakisposóbwułamkusekundyodnaleźćścieżkęonajniższym
koszcienaobszernychmapach.Jeślizaśrozwiązaniemniemusibyćnajlepsza
możliwaścieżka,ajedynieścieżkawystarczającodobra,zajmujeimtojeszcze
mniejczasu.KiedyjużzespółRedTeamzapomocąalgorytmuzaplanowałtrasę
pojazdu,Humveebyłgotowydostartu.
