A * 3 roboti sa navzájom dotýkajú - java, umelá inteligencia, vzdialenosť, robot, heuristika

Jedná sa o všetky 3 roboty, pomenované A, B a C, ktoré sa môžu pohybovať po svojom prostredí pomocou informovaného vyhľadávania. Prostredie obsahuje prekážky. 3 roboti sa musia v určitom okamihu stretnúť tak, že celková vzdialenosť, ktorú prechádzajú, je minimálna.

Aby bol problém trochu výpočtovojednoduchšie, prekážky obmedzíme na obdĺžniky. 3 roboti sú vždy kruhy s polomerom 1. Cieľom je dosiahnuť, aby sa 3 roboty (kruhy) navzájom dotýkali; vzdialenosť medzi stredmi každých dvoch robotov je 1 jednotka. Počas pohybu nesmú roboti preťať žiadnu prekážku. V každom kroku jeden z 3 robotov presunie jednu jednotku z aktuálneho miesta v každom zo štyroch smerov: doľava, doprava, hore a dole. Pohyb z jedného bodu do druhého nesmie prejsť žiadnou prekážkou.

Potrebujem len dobrú heuristickú funkciu, ktorá dokáže priblížiť vzdialenosť medzi 3 robotmi, môžete mi pomôcť, chlapci?

Vyriešil som tento problém, tu je kód Github kód

odpovede:

Tu predpokladám, že chcete minimalizovaťpočet celkových krokov (naraz sa pohybuje iba jeden robot). Ak sa všetky roboty pohybujú súčasne a chcete minimalizovať potrebný čas, riešenie by bolo odlišné. Je tiež potrebné jemné doladenie, pretože roboty by sa mali iba dotknúť, a nie prísť k rovnakému bodu.

Potrebujete vlastne dolnú hranicu, nie znakaproximácia. Dobrá dolná hranica sa dá vypočítať tak, že sa nebudú brať do úvahy prekážky a na prázdnom poli sa skontroluje, koľko pohybov je potrebných. Pretože sa roboty môžu pohybovať iba horizontálne alebo vertikálne, uvažujeme tieto smery osobitne.

Najskôr urobte vodorovný smer.Robot úplne vľavo a vpravo sa musí stretnúť niekde medzi sebou tak nezávisle, kde sa stretne, celkovo musí medzi sebou presunúť vodorovnú vzdialenosť. Ak sa stretnú vo vodorovnej polohe prostredného robota, stred sa nemusí pohybovať. Horizontálnymi krokmi nevyhnutnými v každom prípade je teda horizontálna vzdialenosť medzi robotom úplne zľava a úplne doprava. Nazvime to horizontálne rozpätie.

Podobný argument platí aj pre vertikálny smer.

Celkovo je teda dolná hranica vertikálne rozpätie plus horizontálne rozpätie.

Ak sa každý robot pohybuje súčasne a je toznáme, kde sú prekážky na začiatku (tak známa mapa), a prekážky, ktoré sa pohybujú, by to fungovalo. Uou by bolo potrebné vygenerovať svoju mriežku pomocou algoritmu vlnoplochy. Toto by sa robilo na začiatku pre každého robota. Potom prechádzajte každou mriežkou a pridajte kroky od každého robota. Potom nájdite mriežku s najmenším počtom.