Abstract-I detta papper anser vi att problemet med att upprätthålla synligheten för en rörlig undvikare av en mobil robot, förföljaren, i en miljö med hinder. Vi anser samtidigt begränsad hastighet för både spelare och ett variabelt avstånd separera dem. Till skillnad från våra tidigare insatser [11] ägnar vi särskild uppmärksamhet åt det kombinatoriska problem som uppstår när vi söker efter en lösning genom att besöka flera platser. Vi närmar oss undvikande spårning genom att bryta ner miljön i konvexa regioner. Vi definierar två grafer: den ena kallas den ömsesidiga synlighetsgrafen (MVG) och den andra tillgänglighetsgrafen (AG). MVG ger ett tillräckligt villkor för att hålla rymlingen synlig, medan den rådgivande gruppen för T2S definierar möjliga regioner till vilka antingen förföljaren eller rymlingen kan vända sig. Problemet är inramat som ett icke-kooperativt spel. Vi etablerar existensen av en lösning, baserad på en k − M in approach, för följande givna: miljön, det ursprungliga tillståndet för undvikaren och förföljaren, inklusive deras maximala hastigheter. Vi visar att problemet med att hitta en lösning på detta spel är NP-komplett.
I REF visar författarna att problemet med att avgöra om förföljaren kan hålla sikten synlig i en allmän miljö är minst NP-komplett.
A Complexity result for the pursuit-evasion game of maintaining visibility of a moving evader
{'venue': '2008 IEEE International Conference on Robotics and Automation', 'journal': '2008 IEEE International Conference on Robotics and Automation', 'mag_field_of_study': ['Mathematics', 'Computer Science']}