Abstract Två mobila robotar placeras initialt på samma punkt på en oändlig linje. Varje robot kan röra sig på linjen i båda riktningarna och inte överskrida sin maximala hastighet. Robotarna måste hitta ett stationärt mål placerat på en okänd plats på linjen. Sökningen slutförs när båda robotarna anländer till målpunkten. Målet upptäcks i det ögonblick då någon av robotarna anländer till sin position. Roboten som känner till målets placering kan kommunicera det till den andra roboten. Vi letar efter algoritmen med kortast möjliga söktid (dvs. Det värsta fall då båda robotarna möts vid målet) mätt som en funktion av målavståndet från ursprunget (dvs. den tid som krävs för att färdas direkt från utgångspunkten till målet med enhetshastigheten). Vi överväger två standardmodeller för kommunikation mellan robotarna, nämligen trådlös kommunikation och kommunikation genom möte. När det gäller kommunikation genom möte, en robot lär sig om målet samtidigt dela samma plats med en robot som har denna kunskap. Vi föreslår här en optimal sökstrategi för två robotar inklusive respektive argument med lägre gränser, för hela spektrumet av deras maximala hastigheter. Detta utökar det huvudsakliga resultatet av Chrobak et al. (i: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Aktuella trender i teori och praktik av datavetenskap, SOFSEM, 2015) hänvisar till den exakta komplexiteten av problemet för fallet när hastigheten på den långsammare roboten är minst en tredjedel av den snabbare. I den trådlösa kommunikationsmodellen tas ett meddelande som skickas av en robot omedelbart emot av den andra roboten, oavsett deras nuvarande positioner på linjen. För den här modellen utformar vi en strategi som är optimal när som helst den snabbare roboten är högst 17 + 4 8 23 gånger snabbare än den långsammare. Vi bevisar också att i annat fall erbjuder den trådlösa kommunikationen ingen fördel jämfört med kommunikationen genom att mötas.
För båda typerna av robotars kommunikationsscenarier presenterar REF optimala evakueringsalgoritmer för två robotar med godtyckliga, möjligen distinkta, maximala hastigheter i linjemiljön.
Linear Search by a Pair of Distinct-Speed Robots
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}