Основы теоретической робототехники. Теория толерантных пространств (обзор) — страница 6

  • Просмотров 243
  • Скачиваний 3
  • Размер файла 326
    Кб

итераций граф сойдётся в точку. На рисунках указан диаметр графа  и число доминирования min. ИСХОДНЫЙ ГРАФ. =5 min=4 Рис. 1а I итерация. =5 min=3 Рис. 1б II итерация. =4 min=3 Рис. 1в III итерация. =3 min=2 Рис. 1г IV итерация. =3 min=2 Рис. 1д V итерация. =2 =1 Рис. 1е Очевидно, что толерантное пространство легко можно превратить в топологическое пространство, поскольку это есть пространство метрическое. Целочисленная метрика между двумя

точками есть минимальное число звеньев у допустимой ломаной, которая их соединяет. 4. ЛИНИЯ А. СОСИНСКОГО. ТОЛЕОМОРФИЗМЫ. В основополагающей статье А.Б. Сосинского [10] нас прежде всего интересует понятие толеоморфизма. Толеоморфизм – отношение похожести толерантных пространств, в отличие от изоморфизма линейных пространств и графов. На основе толеоморфизма можно определить отношение толерантности между ТП [10]. Определение. X

и Y называют толеоморфными, если существуют два морфизма , которые: а) почти инъективны: x, x’X f(x)=f(x’) -> x2x’ y, y’Y g(y)=g(y’) -> y2y’ б) почти сюръективны: yY xX f(x)y xX yY g(y)x в) почти обратимы: xX yY f(x)y g(y)2(x) yY xX g(y)x f(x)2(y) (f,g) – толеоморфизм. (f,g) : XY , Y X На рис. 2 приведён пример двух неизоморфных, но толеоморфных пространств. Рис. 2. Пример “2-Швайковский-2“ Теорема Л.В.Келдыш [11,12] говорит о существовании

непрерывного отображения трёхмерного куба на четырёхмерный. А. Б. Сосинский предлагает использовать для кодирования не само открытое монотонное отображение Келдыш, а вложение Келдыш трёхмерного куба в четырёхмерный. Это вложение возникает в промежуточном рассуждении при построении самого отображения. Это вложение является толеоморфизмом. В [10] показано, что отношение толеоморфизма есть отношение толерантности между

толерантными пространствами. 5. ТЕОРИЯ ТЕРРАЙНОВ. Движение РМС задается в террайне  – ограниченной прямоугольной рамкой области с препятствиями, непрозрачными для измерителя и непреодолимыми для МР. Для простоты препятствия представляют собой многоугольники с углами в вершинах в 90 и 270. Подобные модели активно исследовались в ИПМ им.М.В.Келдыша РАН [4,5] и других исследовательских организациях. Пример террайна изображён

на рис. 3. Рис. 3. Пример террайна. R1…R8 – комнаты; а1…а4 – элементы РМС; b1…b5 – неизвестные объекты. Пунктиром показаны возможные перемещения неизвестных объектов Две точки x,y видимы одна из другой (что записывается как x~y), если отрезок [x,y] не пересекает препятствий (но может их касаться). В общем случае террайн Ter = < V , , , ~, [...]>, где V - носитель террайна, (x,y) - исходная евклидова метрика, (x,y) - вторая основная непрерывная