Зведення до дискретного масиву даних

Найбільш очевидним підходом буде відобразити інформацію про об’єкти на двовимірний масив даних. У цьому разі комірки карти, де об’єктів зовсім немає, можуть розглядатися як вільні, а ті комірки, які зайняті об’єктами повністю або частково, як непрохідні (рис. 9.8, б). Єдиним недоліком такого підходу є велика кількість елементів у просторі пошуку.

Задання об’єктів вершинами у зоні прямої видимості

Найбільш критичні елементи об’єктів з погляду алгоритмів пошуку оптимального шляху – це їх вершини. Таким чином, задавши для кожної з вершин вузол зв’язного графу, що їй відповідає, і задавши зв’язки між вузлами, які знаходяться в зоні прямої видимості один від одного, отримуємо прийнятне подання для простору пошуку (рис. 9.8, в). Недоліком такого підходу є те, що вислідна траєкторія буде прокладена близько до вершин об’єктів; це може бути неприпустимим з погляду гарантування безпеки руху.

Метод опуклих багатокутників

Альтернативою попередньому може бути використання методу опуклих багатокутників (рис. 9.8, г). У цьому випадку вільний від об’єктів простір розбивають на опуклі багатокутники. Вузли простору пошуку розміщують у серединах сторін, вільних від об’єктів, і з’єднуються з іншими вузлами за прямої видимості. Таке розбиття хоча й гарантує безпечну відстань до блокуючих об’єктів, але не забезпечує найкоротшої траєкторії.

^a б в

г _д е

Рис. 9.8. Перешкоди в суцільному просторі та методи перетворення простору пошуку:

а – перешкоди в суцільному просторі; б – зведення до дискретного масиву даних;

в – задання об’єктів вершинами у зоні прямої видимості; г – метод опуклих багатокут-ників; д – метод послідовного розбиття простору; е – метод узагальнених циліндрів

Метод послідовного розбиття простору

Зменшуючи крок дискретизації під час перетворення простору пошуку до дискретного вигляду можна отримати будь-яку наперед задану точність подання перешкод, але необмежено зростаючу кількість елементів у просторі пошуку. Збільшуючи ж крок, точність подання перешкод може виявитись незадовільною. Компромісним розв’язанням може стати метод адаптивного розбиття простору. Під час

першого проходу крок дискретизації вибирають досить великим. Надалі «подрібнюються» тільки ті елементи, які частково містять перешкоди. Результат такого адаптивного розбиття показано на рис. 9.8, д.

Метод узагальнених циліндрів

Вільні простори між сусідніми перешкодами розглядають як циліндри, форма яких змінюється вздовж їх осей. Такі осі будують для кожної пари сусідніх перешкод і меж простору пошуку й розглядають як можливі елементи траєкторій руху.

Всі описані алгоритми дискретизації суцільного простору мають певні переваги і недоліки, що визначають сфери їх застосування. У деяких випадках конкретний вид алгоритму побудови зв’язаних графів повністю визначається поставленим завданням. Наприклад, для прокладення оптимальної траєкторії руху вулицями міста, кожне перехрестя можна представити як вузол відповідного графу, а зв’язуючим елементом для такого графу будуть вулиці.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Вороновский Г. К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности [Текст] / Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев. – Харьков: Основа, 1997. – 112 с. – Библиогр.: с. 78–81. – 800 экз. – ISBN 5–7768–0293–8.

2. Уськов А. А.Интеллектуальные технологии управления:искус-ственные нейронные сети и нечеткая логика [Текст] / А. А. Уськов, А. В. Кузьмин. – М.: Горячая линия – Телеком, 2004. – 143 с. – Биб

лиогр.: с. 124–141. – 1000 экз. – ISBN 5–93517–181–3.

3. Рутковская Д. Нейронные сети,генетические алгоритмы и не-четкие системы [Текст] / Д. Рутковская, М. Пилиньский, Л. Рутковский. – М.: Горячая линия – Телеком, 2004. – 452 с. – Библиогр.:

с. 379–380. – 1500 экз. – ISBN 5–93517–103–1.

4. P. Wasserman. Neural computing: theory and practice / VanNostrand Reinhold, New-York, 1989.

5. J. S. Albus and A.M. Meystel. Engineering of Mind: AnIntroduction to the Science of Intelligent Systems / Wiley, New York, 2001.

6. J. S. Albus and A. M. Meystel. Intelligent Systems: Architecture,Design, and Control / Wiley, New York, 2002.

7. A. P. Engelbrecht. Computational Intelligence: An Introduction /Wiley, Chichester, U.K., 2002.

8. R. Babuska. Fuzzy Modeling for Control / Kluwer AcademicPublishers, Boston, 1998.

9. L. Fausett. Fundamentals of Neural Networks: Architectures,Algorithms and Applications / Prentice Hall, Englewood Cliffs, NJ, 1997

10. S. Haykin. Neural Networks: A Comprehensive Foundation /

Macmillan, New York, 1994.

11. C. R. Reeves and J.W. Rowe. Genetic Algorithms Principles and

Perspectives: A Guide to GA Theory / Kluwer, Boston, 1997.

12. R. A. Aleev and R. R. Aleev. Soft Computing and its Applications /

World Scientific, Singapore, 2001.

13. L. A. Zadeh. Fuzzy sets / Information and Control, 8:338-353,

1965.

14. H. Bandemer and S. Gottwald. Fuzzy Sets, Fuzzy Logic Fuzzy

Methods with Applications / John Wiley & Sons, Chichester, 1995.

15. R. J. Schalkoff. Artificial Neural Networks / McGraw-Hill, New

York, 2002.

16. A. B. Badiru and J. Y. Cheung. Fuzzy Engineering Expert Systems

with Neural Network Applications / John Wiley, New York, NY, 2002.