Abstract-Vi överväger utmaningen att planera en minimilängd väg från en initial position till en slutlig position för en rotorfarkost. Stigen finns i ett 3-dimensionellt euklideiskt utrymme som innehåller ett geometriskt hinder. Vi baserar vår strategi på synfält som har använts i stor utsträckning för färdplansbaserad vägplanering i tvådimensionellt Euclidean utrymme. Att generalisera till 3-dimensionellt utrymme är inte enkelt, om inte en synlighetsgraf skapas som, när sök, bara kommer att ge en ungefärlig minsta längd väg. Vårt tillvägagångssätt genererar en sådan synlighetsgraf som består av en hindergraf och två stödjande grafer. Hindergrafen genereras genom att man tillnärmar ett nät runt konfigurationsutrymmets hinder, som byggs från konvext skrov på dess arbetsutrymmesmotsvarighet. De stödjande graferna genereras genom att man hittar stödlinjerna mellan den ursprungliga eller slutliga positionen och maskan. En approximation till den optimala sökvägen kan därefter hittas med hjälp av en befintlig grafsökalgoritm. Det framlagda tillvägagångssättet är lämpligt för fullt kända miljöer med ett enda verkligt 3-dimensionellt (inte bara "höjt" 2-dimensionellt) hinder. Ett exempel på att generera en nästan minsta längdbana för en liten helikopter som kör nära en byggnad visas. Vägplanering och bangenerering är grundläggande områden för UAS-utveckling och både ger möjlighet att räkna ut ett sätt att effektivt och säkert resa genom en miljö med en rad begränsningar. För uppgifter som övervakning, inspektion, flygkartläggning osv. används i allt högre grad småskaliga autonoma helikoptrar. I många sådana uppgifter är det fördelaktigt att verka i närheten av hindren eller att följa deras yta. Den praktiska användningen av det presenterade arbetet är att få fram metoder för banplanering som kan användas för att driva en småskalig helikopter i en miljö som begränsas av hinder. Den metod som presenteras är nära-optimal, det vill säga kunna producera en stig nära den euklideiska kortaste vägen inne i ett utrymme. Detta utrymme begränsas av ett enda hinder så att inga delar av fordonet får korsa hindret när som helst. I detta utrymme representeras fordonet av dess gränsande sfär, som är centrerad i mitten av massan. Det framlagda tillvägagångssättet för vägplanering använder synbarhetsdiagram (VG). Avhandlingar VG bygger på att beskriva hindren i ett konfigurationsutrymme (CS), som i sin tur baseras på arbetsytan (WS). Det viktigaste bidraget från detta dokument är att skapa dessa hinder för KS och VG. WS-hindret kan byggas från vilken uppsättning hörn som helst, t.ex. ett punktmoln från data som samlats in. WS-hindret görs konvext eftersom icke-konvexa delar inte är relevanta vid sökning av VG efter en lösning. I själva verket, när du beräknar den kortaste vägen mellan två punkter i CS, den kortaste vägen är en serie anslutna kanter som är antingen på konvexa skrovet av hindret, eller tangenter från punkterna till hindret. Tidigare arbete om hur man praktiskt, automatiskt och effektivt genererar ett konfigurationsutrymme från ett 3D-punktmoln i WS verkar begränsat till att bygga primitiva fasta eller geometriska representationer, och i många vägplaneringspublikationer antas ett befintligt konfigurationsutrymme helt enkelt. Synlighetsgrafer för 2D-vägplanering har använts i stor utsträckning. Att hitta en optimal lösning på det allmänna stigplaneringsproblemet i 3D är dock NP-komplett, se [1], [2]. Svårigheten med problemet är att den kortaste vägen runt ett polyhedral hinder inte i allmänhet passerar bara hörn av polyhedron, men också pekar någonstans på kanterna av polyhedron. Konceptet att lägga till ytterligare hörn längs dessa kanter i konfigurationsutrymme så att inga kant hörn är fördelade mer än en specificerad maximal längd införs av Lozano-Perez och Wesley [1]. Detta tillvägagångssätt leder i allmänhet till en god approximation till den optimala vägen. Lozano-Perez [3] presenterar en algoritm för 2D-fallet som använder Minkowski-summan (se [4] för detaljer om Minkowski-summan) för att generera ett CS-hinder från ett polygonalt hinder och ett polygonalt fordon. Medan CS hinder kan genereras genom att tillnärma fordonet med en geodesisk kupol, hinder beskrivs med en sekvens av algebraiska ekvationer, vilket gör optimeringsproblemet svårt att lösa utan att tillgripa numeriska metoder. Även Bajaj och Kim [5] beskriver algebraiska algoritmer för att representera gränsen av CS-hinder som fläckar av kvadratiska ytor. Vi föreslår en metod för att generera en VG från 1) en punktmoln som representerar WS hinder, 2) ett fordon avgränsande sfär med radie r bs, och 3) en initial och slutlig position för fordonet. Den generaliserade synlighetsgrafen VG(N, L) innehåller en noduppsättning N och en länkuppsättning L av länkar mellan nodpar. Varje nod i grafen tilldelas en möjlig konfiguration (eller position), och varje länk representerar en synlig (linjär) förbindelse mellan dem. VG består av två delar; en diagram för hindersynlighet VG o som länkar samman nodepar nära hinderytan, och en stödjande synlighet 2012 Intelligent Vehicles Symposium
Till exempel Scholer et al. REF konstruerar en tredimensionell synkurva för UAV, bestående av ett hinder, och två stödjande grafer.
Generating approximative minimum length paths in 3D for UAVs
{'venue': '2012 IEEE Intelligent Vehicles Symposium', 'journal': '2012 IEEE Intelligent Vehicles Symposium', 'mag_field_of_study': ['Mathematics', 'Computer Science']}