Przechwytywanie obiektów poruszających się z ograniczoną prędkością

• Autorzy: Wrona Ł.

Warianty tytułu

EN

Capturing objects moving with bounded speed

• Języki publikacji: PL

Abstrakty

PL

Krawędziowa liczba przeszukiwawcza grafu informuje nas ilu mobilnych agentów, przykładowo jednostek policji, jest niezbędnych do przechwycenia poruszającego się z dowolnie dużą prędkością uciekiniera w danym grafie. Podczas praktycznych zastosowań modelu w systemach bezpieczeństwa rzadko jednak spotyka się jednostki poruszające się z nieograniczoną prędkością. W pracy tej pokazujemy, że agenci mogą wykorzystać fakt ograniczonej prędkości uciekiniera w celu poprawienia strategii jego przechwytywania. Zaproponowany zostaje dyskretny w czasie model analizy przechwytywania obiektów poruszających się w grafie z ograniczoną prędkością.

EN

Edge search number of a graph is a value, that provides us with information as to how many mobile agents, for instance police units, are required to capture an arbitrary fast evader in a given graph. In practical application of this model in security systems units, that do not have any boundary on their speed, are rarely met. In this paper we show, that agents may use the fact of evaders bounded speed in order to improve their search strategy. We present a discrete-time model which may be used to analyze interception of objects moving with bounded speed.

Słowa kluczowe

PL

model z ograniczoną prędkością; zasady ruchu uciekiniera; zasady ruchu agentów; dyskretny czas

EN

moving object; bounded speed; mobile agents; evaders bounded speed; search strategy

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 427--434
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Wrona Ł.

• Katedra Algorytmów i Modelowania Systemów Informatycznych, Politechnika Gdańska

Bibliografia

• [1] Parsons T.D.: Pursuit-evasion in a graph, Lecture notes in mathematics 642, 1976, s. 426-44l.
• [2] Parsons T.D.: Search number of a connected graph, Proceedings of the 9th Southeastern Conference on Combinatorics, Graph Theory and Computing, 1978, s. 549-554.
• [3] Alspach B.: Searching and sweeping graphs: A brieJ survey, Second Prairie Discrete Mathematics Workshop, 2004.
• [4] Megiddo N., Hakimi S. L., Garey M. R., Johnson D. S., Papadimitriou, C. H.: The complexity of searching a graph, J. ACM 35,1988, s 18-44.
• [5] Golovach P.A., Petrov NN.: The search number of a complete graph, Vestn. Leningr. Univ., Math. 19, no. 4, 1986,s. 15-19.
• [6] LaPaugh A.: Recontamination does not help to search a graph, J. ACM 40, 1993, s. 224-245.
• [7] Isaacs R.: Differential games, Courier Dover Publications, 1999.
• [8] Isler I.V.: Algorithms for distributed and mobile sensing, Ph.D. thesis, University of Pennsylvania, 2004.
• [9] Wrona Ł.: Metody przechwytywania poruszających się obiektów przez mobilnych agentów, Master thesis, Technical Univeristy of Gdansk, 2006