About one method of retracing on a plane

Prombles in programming 2013; 3: 117-124

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
1. Verfasser:	Yalovets, A.L.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут програмних систем НАН України 2025
Schlagworte:	UDC 004.942+623.465
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/759
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-759
record_format	ojs
resource_txt_mv	ppisoftskievua/23/3af679d03831b36b7cc9768c0561b523.pdf
spelling	pp_isofts_kiev_ua-article-7592025-06-21T15:30:49Z About one method of retracing on a plane Про один метод переслідування на площині Yalovets, A.L. UDC 004.942+623.465 УДК 004.942+623.465 Prombles in programming 2013; 3: 117-124 Розглядається проблема формування стратегій переслідування на площині для агентів. Пропонується метод переслідування, який зводиться як до метода паралельного зближення, так і до метода окружності Аполлонія. Описуються функціональні можливості прототипу системи «Навігація», в якому реалізовано запропонований метод переслідування для випадку «один переслідувач – один утікач».Prombles in programming 2013; 3: 117-124 Інститут програмних систем НАН України 2025-06-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/759 PROBLEMS IN PROGRAMMING; No 3 (2013); 117-124 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2013); 117-124 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2013); 117-124 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/759/811 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-06-21T15:30:49Z
collection	OJS
language	Ukrainian
topic	UDC 004.942+623.465
spellingShingle	UDC 004.942+623.465 Yalovets, A.L. About one method of retracing on a plane
topic_facet	UDC 004.942+623.465 УДК 004.942+623.465
format	Article
author	Yalovets, A.L.
author_facet	Yalovets, A.L.
author_sort	Yalovets, A.L.
title	About one method of retracing on a plane
title_short	About one method of retracing on a plane
title_full	About one method of retracing on a plane
title_fullStr	About one method of retracing on a plane
title_full_unstemmed	About one method of retracing on a plane
title_sort	about one method of retracing on a plane
title_alt	Про один метод переслідування на площині
description	Prombles in programming 2013; 3: 117-124
publisher	Інститут програмних систем НАН України
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/759
work_keys_str_mv	AT yalovetsal aboutonemethodofretracingonaplane AT yalovetsal proodinmetodpereslíduvannânaploŝiní
first_indexed	2025-07-17T09:53:48Z
last_indexed	2025-07-17T09:53:48Z
_version_	1838409829567168512
fulltext	Прикладні засоби програмування та програмне забезпечення © А.Л. Яловець, 2013 ISSN 1727-4907. Проблеми програмування. 2013. № 3 117 УДК 004.942+623.465 А.Л. Яловець ПРО ОДИН МЕТОД ПЕРЕСЛІДУВАННЯ НА ПЛОЩИНІ Розглядається проблема формування стратегій переслідування на площині для агентів. Пропонується метод переслідування, який зводиться як до метода паралельного зближення, так і до метода окруж- ності Аполлонія. Описуються функціональні можливості прототипу системи «Навігація», в якому реа- лізовано запропонований метод переслідування для випадку «один переслідувач – один утікач». Вступ У роботі [1] запропоновано поста- новку задачі переслідування на площині з точки зору агентного підходу та визначено перелік методів, які необхідно розробити. До таких методів, зокрема, належать мето- ди формування стратегій поведінки агента- переслідувача та агента-утікача. Мета да- ної роботи – викладення одного з можли- вих методів переслідування на площині, який доцільно покласти в основу стратегії поведінки як агента-переслідувача, так і агента-утікача. 1. Короткий огляд відомих стратегій переслідування Відомі стратегії переслідування здебільшого розроблено для військового призначення (в рамках досліджень щодо наведення ракет на рухому ціль [2–4]). Як показано в [4], відомі методи наведення можна розподілити на дві підгрупи:  методи з фіксованим положенням не- обхідного направлення вектора швидкості відносно лінії ракета – ціль (до таких ме- тодів належать метод погоні та метод по- стійного випередження);  методи зі змінним положенням необ- хідного направлення вектора швидкості ві- дносно лінії ракета – ціль (до таких методів належать метод пропорційного зближення та метод паралельного зближення). Методом погоні називають такий метод наведення, при якому в кожний мо- мент часу вектор швидкості ракети на- правлений на ціль. Використання методу погоні як стратегію переслідування приз- водить до того, що траєкторія польоту ра- кети буде криволінійною за винятком двох окремих випадків (при пуску ракети точно вдогін цілі або точно назустріч цілі). Методом постійного випереджен- ня (або методом наведення з постійним кутом випередження) називають такий метод наведення, при якому необхідний рух ракети визначається умовою, що на протязі всього часу польоту ракети до точ- ки зустрічі кут між вектором швидкості ракети і лінією ракета – ціль (кут випере- дження) залишається постійним. Викорис- тання методу постійного випередження як стратегію переслідування призводить до того, що траєкторія польоту ракети буде криволінійною (хоча її криволінійність бу- де меншою, ніж у випадку використання методу погоні). Методом пропорційного зближення називають такий метод наведення, при яко- му на протязі всього часу польоту ракети до цілі кутова швидкість повороту вектора швидкості ракети залишається пропорцій- ною кутовій швидкості лінії ракета – ціль. Використання методу пропорційного збли- ження як стратегії переслідування призво- дить до того, що траєкторія польоту ракети займає проміжне місце між траєкторією за методом погоні та траєкторією за методом паралельного зближення (див. далі). Методом паралельного зближення називають такий метод наведення, при якому на протязі всього часу польоту ра- кети до точки зустрічі лінія ракета – ціль залишається паралельною заданому напра- вленню. За даним методом ракета направ- ляється не на ціль, а на точку зустрічі ра- кети з ціллю. Використання методу пара- лельного зближення як стратегії переслі- дування дає найкращі результати в порів- нянні з вищенаведеними методами наве- дення, оскільки дозволяє отримати пряму траєкторію польоту ракети (рис. 1). Прикладні засоби програмування та програмне забезпечення 118 α P0 E0 φ VP VE VEsinφ VPsinα P1 E1 E2 P2 P3 E3 P4 E4 Рис. 1 Сутність метода паралельного зближення Стратегія переслідування, яка від- повідає методу паралельного зближення, задається за допомогою рівняння (1):  sinsin EP VV  . (1) Таким чином, найбільш прийнят- ним відомим методом наведення є метод паралельного зближення, тим більше [5], що за своїми властивостями він відповідає методу окружності Аполлонія. Разом з тим, у даного метода (як і у метода окруж- ності Аполлонія) є певний недолік, який не дозволяє нам задіяти саме ці методи як стратегію переслідування: дані методи явно не використовують ортогональну си- стему координат, використання якої, як показано в [1], необхідно з точки зору пос- тановки задачі переслідування на площині. 2. Метод переслідування на пло- щині Пропонований метод переслідуван- ня засновується на наступній постановці: два об’єкти (утікач та переслідувач) знахо- дяться у стані простого руху, при цьому задано (рис. 2): поточні координати утіка- ча (точка Е), поточні координати переслі- дувача (точка Р), напрям руху утікача (кут E ), швидкість руху утікача ( Ev ) та шви- дкість руху переслідувача ( Pv ). Інтуїтивно зрозуміло, що утікач та переслідувач зустрінуться в деякій точці С (в даному випадку за умови, якщо EP vv  ) через певний час t (тобто час руху об’єктів від точок Е і Р до точки С є конс- тантою). Крім того, очевидно, що шляхи EL та PL руху об’єктів можуть бути ви- ражені через їх швидкості та час: tvL EE  ; tvL PP  (передбачається, що швидкості руху об’єктів постійні). P E C φαP αE LE LP K S M Y Y' X' X D F G φ Рис. 2. Сутність пропонованого методу переслідування на площині Прикладні засоби програмування та програмне забезпечення 119 Як невідомі параметри виступають: шуканий напрям руху переслідувача (кут P ); довжина шляху утікача ( EL або дов- жина променя ЕС); довжина шляху перес- лідувача ( PL або довжина променя РС); час, необхідний для досягнення об’єктами точки С; координати точки С. Очевидно, що ця задача належить до задач з області аналітичної геометрії на площині. Для рішення задачі пересліду- вання на площині важливо обчислити кут P , що задає напрям руху переслідувача. Знаючи цей кут, нескладно обчислити всі інші невідомі параметри задачі. Виконаємо додаткові геометричні побудови (див. рис. 2). Очевидно, що пря- мі ЕС і РС можна розглядати як радіуси двох окружностей, що перетинаються в точках С і D. Побудуємо ці окружності й прокладемо для них осі координат XЕY та X'РY'. Проведемо січну SM через точки С і D. З’єднаємо точки Р і D прямою. Очевид- но, що утворений в результаті трикутник РDC є рівнобедреним. Ясно, що висота трикутника РК пройде також і через точку Е. При цьому висота РК перетне осі абсцис Х та Х' під одним і тим же кутом  . Очевидно, що 2 2)180( x y tg   і звід- си ми можемо обчислити кут  (відстані х2 та y2 легко обчислити через координати точок Е і Р). В свою чергу,  PP L)(sin  zLEE  )sin(  , де z – відрізок КС. Перетворюючи це рівняння, отримуємо: )sin()(sin E P E P L L   . Враховуючи, що tvL EE  і tvL PP  , остаточно маємо: )sin()sin( E P E P v v   . (2) Таким чином, ми показали, що кут P , який задає напрям руху переслідувача, легко обчислюється. Покажемо, що запропонований ме- тод зводиться до методу окружності Апол- лонія. Для цього досить показати, що по- будова окружності Аполлонія відповідає загальним принципам, покладеним в осно- ву запропонованого метода. На даних, по- казаних на рис. 2, побудуємо окружність Аполлонія (рис. 3). P E C φαP φ αE LE LP K S M Y Y' X' X D F Ya Xaαa φ A RA Окружність Аполлонія φ Рис. 3. Зведення пропонованого методу до методу окружності Аполлонія Прикладні засоби програмування та програмне забезпечення 120 По-перше, за правилами побудови окружності Аполлонія центр цієї окружно- сті (точка А) завжди буде належати прямій РК. По-друге, точка зустрічі С утікача та переслідувача завжди буде належати окружності Аполлонія (це так звана точка Аполлонія). Очевидно, що пряма, яка з’єднує точки А та С, відповідає радіусу AR окружності Аполлонія. Легко помітити (див. рис. 3), що і в даному випадку вико- нується співвідношення:  PP L)(sin  ,)(sin)(sin zRL AAEE   де z – відрізок КС. В зв’язку з тим, що КС = КD, стає очевидним, що трикутник АСD є рів- нобедреним, з чого випливає, що всі три окружності (дві окружності, розглянуті в пропонованому методі, та окружність Аполлонія) мають в точності одні й ті ж самі точки перетину С та D. В свою чергу, легко показати, що запропонований метод зводиться до метод паралельного зближення. Так, з (2) випли- ває, що )sin()sin( EEPP vv   . Позначимо (див. рис. 2) кут РЕС через  . Ясно, що )(180 E  . Оскільки  sin)180sin(  , то очевидно, що )(sinsin E  . Звідси випливає справе- дливість рівняння:  sin)sin(  EPP vv . Порівнюючи отримане рівняння з виразом (1), легко помітити їх ідентичність (див. також рис. 1). На основі запропонованого метода переслідування на площині можна сфор- мувати стратегію поведінки переслідувача. Очевидно, що визначення доцільного на- пряму руху переслідувача за наведеним методом повністю відповідає рішенню за методом паралельного зближення і дає в точності ті ж самі результати. Як наслідок, стратегія поведінки переслідувача орієнто- вана на постійний аналіз поведінки утіка- ча, визначення в момент зміни поведінки утікача доцільного кута напрямку свого руху та, в наслідок цього, динамічне коре- гування своєї поведінки. Отримані результати дозволяють та- кож зробити висновки щодо доцільної стратегії поведінки утікача. Очевидно (див. рис. 2), що найдовший шлях переслідувач пройде, якщо утікач буде рухатись у на- прямку EG. Так, якщо порівняти відстані РС та PG, то ясно, що PG більше РС на ві- дрізок FG. Звідси випливає доцільна стра- тегія поведінки утікача: він має корегувати напрям свого руху таким чином, щоб він максимально наближався до напрямку, що задається променем, побудованим за на- прямком від переслідувача до утікача. 3. Прототип системи моделювання переслідування на площині На основі розробленого методу пе- реслідування на площині створено прото- тип системи «Навігація», версія 1.0 (надалі – Система). Призначення Системи полягає в дослідженні поведінки агентів для ви- падку «один переслідувач – один утікач» (рис. 4). Введення вхідних параметрів Введення параметрів маневрування Введення точок маневрування в реальному масштабі часу Запуск процесу переслідування Відобразити окружності Збільшити Зменшити Рис. 4. Робоче вікно та склад основних кнопок панелі інструментів Системи Прикладні засоби програмування та програмне забезпечення 121 Робота Системи починається з на- тискання кнопки «Введення вхідних пара- метрів». В результаті відкривається графі- чне вікно та діалог параметризації об’єктів (рис. 5), в якому користувач задає відпові- дні параметри утікача (об’єкта 1) та перес- лідувача (об’єкта 2). Користувачу також надається підказка щодо рекомендованої швидкості переслідувача (з метою забез- печення існування рішення задачі). Після завершення параметризації об’єктів та на- тискання на кнопку «ОК», у графічному вікні відображаються агенти та їх потен- ційні траєкторії (рис. 6). Рис. 5. Діалог параметризації об’єктів Рис. 6. Розташування агентів та траєкторії їх потенційного руху Прикладні засоби програмування та програмне забезпечення 122 За допомогою кнопок панелі ін- струментів «Введення параметрів манев- рування» та «Введення точок маневруван- ня в реальному масштабі часу» користувач може задавати різні варіанти маневрування утікача. В першому випадку користувач вказує точки зміни курсу утікача (рис. 7) до початку процесу переслідування. Піс- ля завершення введення параметрів та натискання на кнопку панелі інструмен- тів «Запуск процесу переслідування» відбувається переслідування у відповідно- сті до запланованого маневрування утіка- ча (рис. 8). У другому випадку (за допомогою кнопки «Введення точок маневрування в реальному масштабі часу») користувач вказує точки зміни курсу утікача (рис. 9) безпосередньо в процесі переслідування, тобто в даному випадку є можливість швидко реагувати на зміни поточної ситу- ації з метою ускладнення процесу переслі- дування для переслідувача. Рис. 7. Введення параметрів маневрування Рис. 8. Моделювання процесу переслідування з запланованим маневруванням Прикладні засоби програмування та програмне забезпечення 123 Рис. 9. Моделювання процесу переслідування з маневруванням у реальному масштабі часу В ході моделювання процесу перес- лідування у користувача є можливість до- відково відобразити три окружності (в то- му числі й окружність Аполлонія – див. також рис. 3), які побудовані з урахуван- ням поточних положень агентів та динамі- чно змінюються (рис. 10). В процесі вико- ристання системи користувачу надаються додаткові сервіси, пов’язані з масштабу- ванням зображень. Систему реалізовано на мові логіч- ного програмування PDC Visual Prolog 5.2. Рис. 10. Демонстрація зведення запропонованого метода до метода окружності Аполлонія Прикладні засоби програмування та програмне забезпечення 124 Висновки Узагальнюючи вищевикладене, мо- жна стверджувати, що розроблений метод переслідування на площині дозволяє сфо- рмувати доцільні стратегії поведінки як агента-переслідувача, так і агента-утікача. На наш погляд, вагомою перевагою запро- понованого метода перед методами- аналогами є те, що він ґрунтується на ви- користанні ортогональної системи коор- динат, що є важливим для вирішення задач моделювання процесів маневрування аген- тів. Успішність такого моделювання наоч- но продемонстрована в створеному прото- типі системи «Навігація». 1. Яловець А.Л. До постановки задачі переслідування на площині // Проблеми програмування. – 2013. – № 2. –С. 95–100. 2. Куркоткин В.И., Стерлигов В.Л. Самона- ведение ракет. – М.: ВоенИздат, 1963. – 89 с. 3. Локк А.С. Управление снарядами. – М.: Гос. изд-во технико-теоретической литера- туры, 1957. – 775 с. 4. Неупокоев Ф.К. Стрельба зенитными ракетами. – М.: ВоенИздат, 1991. – 343 с. 5. Петросян Л.А., Рисхиев Б.Б. Преследова- ние на плоскости. – М.: Наука, 1991. – 91 с. Одержано 10.08.2012 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, Проспект Академіка Глушкова, 40. Тел.: (044) 526 1538. E-mail: yal@isofts.kiev.ua mailto:yal@isofts.kiev.ua

About one method of retracing on a plane

Institution

Ähnliche Einträge