Днк наномеханические роботы и вычислительные устройства

Вид материала

Документы

Подобный материал:

• Программа-минимум кандидатского экзамена по специальности 05. 12. 13 «Системы, сети, 121.7kb.
• Программа-минимум кандидатского экзамена по специальности 05. 12. 13 «Системы, сети, 151.82kb.
• Домашние роботы, 181.38kb.
• Программа-минимум кандидатского экзамена по специальности 05. 12. 14 «Радиолокация, 134.92kb.
• Программа-минимум кандидатского экзамена по специальности 05. 12. 14 «Радиолокация, 236.33kb.
• Концепция: техники активации ДНК скрытые (виртуальные) структуры днк: множественные, 1618.54kb.
• В. А. Климёнов 2010 г. Рабочая программа, 267.99kb.
• Международная конференция «Microcad-2011», секция «Информатика и моделирование», 11.06kb.
• Учебно-методический комплекс дисциплины вычислительные системы, сети и телекоммуникации, 338.43kb.
• Определение: генетический код это система записи информации о последовательности расположения, 51.8kb.

5. Наноинформатика


Развитие бионанотехнологий ставит перед компьютерными науками широкий спектр новых задач. Это моделирование наноустройств и их отдельных узлов на этапе разработки, симуляция работы наноустройств, управление наносистемами и т.д.

Существенное внимание уделяется исследованиям, направленным на создание алгоритмов, моделей и симуляторов для разработки наноустройств на биохимическим уровне. На сегодняшний день разработано несколько симуляторов для биохимических реакций (см. [1] – [6]). В работах [7], [8] предложены алгоритмы анализа некоторых аспектов взаимодействия молекул ДНК. В [9] – [12] описан ряд подходов к моделированию поведения одиночной последовательности ДНК на основе метода Монте-Карло. Методы моделирования РНК рассматривались в работах [13] – [15]. В [16] – [23] разработаны алгоритмы вычисления концентрации молекул ДНК в зависимости от возможных реакций. Большое внимание уделяется исследованию различных моделей полимеризации ДНК [24] – [47]. В работах [48] – [54] исследуются вопросы моделирования ДНК на основе броуновской динамики. Рассматривался также вопрос о моделировании событий: гибридизации, дегибридизации, перемещения [55].

На основе анализа молекулярной коммуникации естественных молекулярных систем (см. [56] – [58]) разрабатываются модели молекулярной коммуникации для искусственных молекулярных систем и наноустройств (см. [59] – [62]).

Весьма важным представляется рассмотрение вопросов разработки, моделирования и управления на уровне, абстрагирующемся от биохимической природы явлений, поскольку это позволяет оперировать общими понятиями для ДНК наномеханических устройств и обычных механических роботов. Это позволяет привлечь для разработки наномеханических устройств модели классической робототехники. При этом следует отметить, что в отдельных случаях возможен полный перенос существующих робототехнических моделей на наноуровень, а в некоторых случаях необходима существенная ревизия, добавляющая в модели принципиально новые краски. Не ставя перед собой задачу дать полный анализ применимости существующих робототехнических теорий к наномеханическим устройствам, мы остановимся лишь на нескольких концепциях с акцентом на различия между макроуровнем и наноуровнем. В частности, для разработки систем управления и коммуникации для наномеханических устройств представляют существенный интерес соответствующие модели теории искусственного интеллекта, относящиеся к так называемому Bottom – Up AI. В первую очередь к числу таких моделей следует отнести

• модели искусственного интеллекта на основе локальных предпочтений (см. [63] – [68]);
  
• системы реактивного управления, применяемые для разработки архитектуры автономных систем роботов, функционирующих под контролем распределенных систем управления (см. [69] – [79]);
  
• теория возникновения и эволюции языка и сознания как единой адаптивной динамической системы (см. [80] – [83]);
  
• теория самоорганизующихся языков (см. [84] – [89]);
  
• исследования в области ассоциации символьной и аналоговой информации (см. [90] – [98]);
  
• теория возникновения предпочтений и функциональности (см. [99] – [108]);
  
• теория автономности и автономных агентов (см. [109] – [114]).
  

Раздел искусственного интеллекта Bottom – Up AI по своей идейной направленности совпадает с нанотехнологиями, поскольку в обоих случаях распространение управления предполагается снизу вверх. Однако перенос моделей Bottom – Up AI на системы наномеханических роботов сопряжен с довольно серьезными трудностями. Основная трудность заключается в том, что формирование новых знаний и/или адаптация имеющихся приведет к изменению физических параметров наномеханических устройств: если изменение содержимого карты памяти обычного робота на может существенно повлиять на механические характеристики устройства, то в случае наномеханического робота произойдет изменение атомно-молекулярной структуры, с которым желательно считаться. Другая важная проблема связана с тем, что генетический материал весьма подвержен точечным мутациям. Соответственно невозможно построить эффективную систему управления ДНК наномеханическим роботом, исходя из предположения, что самопроизвольное изменение структуры робота – поломка. Еще одна проблема заключается в том, что искусственно синтезированная ДНК, попадая в живую клетку, рассматривается клеткой как ДНК (что неудивительно…) и как следствие может быть подвергнута процедуре копирования. Соответственно системы управления, разрабатываемые для ДНК наномеханических роботов должны учитывать плановые отказы роботов, связанные с копированием, а также возможность появления копий роботов или их отдельных узлов. Кроме перечисленных проблем, адаптация систем управления для нанороботов сопряжена с необходимостью учета возможности отторжения иммунной системой. С другой стороны, некоторые из возникающих проблем при определенных условиях могут быть превращены в преимущества. Например, создавая хранилище знаний для расширения функциональности наноробота, мы расширяем его функциональность уже самим фактом появления хранилища. На первый взгляд это сомнительное преимущество, поскольку дополнительная информация, сообщаемая самой конструкцией хранилища может быть сама размещена в хранилище. Однако это не всегда так. В частности, для ряда классов трансдьюсеров языки, печатаемые этими трансдьюсерами, не распознаваемы трансдьюсерами из этих классов [115]. Таким образом, при грамотном подходе к построению хранилища информации для наноробота может оказаться, что конструкция хранилища будет более сложной информацией, чем то, что в нем хранится. Совершенно очевидно, что данный факт нельзя не учитывать при разработке систем коммуникации для нанороботов. Работа иммунной системы при определенных условиях тоже может быть положительной. Иммунная система достаточно хорошо изучена. Естественная иммунная система представляет собой сложный комплекс механизмов защиты от патогенных организмов. Основные цели иммунной системы: распознавание всех клеток организма, классификация их по принципу «свой – чужой», классификация чужих клеток по степени их опасности, нахождение подходящих механизмов защиты от опасных чужих клеток, запуск механизмов защиты. Иммунная система, работающая на клеточном уровне, состоит из клеток, называемых лимфоцитами [116]. Лимфоциты делятся преимущественно на две группы: T-клетки и B-клетки. Лимфоциты разных типов могут совместно бороться с опасными чужими клетками, либо действовать на лимфоциты другого типа, усиливая или понижая их активность. Когда лимфоциты обнаруживают чужую клетку, они начинают производить антитела, предназначенные для уничтожения или нейтрализации чужой клетки. Информация о чужой клетке сохраняется в памяти иммунной системы. Поэтому повторное вторжение иммунная система будет отражать более успешно. Кроме иммунной системы, функционирующей на клеточном уровне, существует иммунная система, работающая внутри клетки. Эта система состоит из молекул РНК и ферментов, а также некоторой «базы знаний», записанной в ДНК. Деятельность этой системы сводится к уничтожению чужеродного или бракованного генетического материала, а также выработке механизмов компенсации мутаций. Хотя конструктивные элементы иммунных систем клеточного и субклеточного уровней существенно отличаются, принцип их функционирования отличается мало. Естественные иммунные системы дают нам интересный пример эффективной распределенной системы, позволяющей решать сложные вычислительные задачи. На сегодняшний день существует ряд теорий [117] – [119] и математических моделей [120], [121] для объяснения феномена иммунитета. Имеется ряд компьютерных моделей [122] – [124] для симуляции различных частей иммунной системы. Разработано также несколько моделей интеллектуальных вычислений для решения алгоритмических проблем [116], [117], [120], [125] – [130]. Таким образом, вместо попыток преодоления иммунной системы можно использовать ее как естественный вычислительный механизм. К сожалению, большинство существующих моделей Bottom – Up AI рассматривают среду, в которой функционирует робот, преимущественно как набор препятствий. В то же время ДНК наномеханические роботы теоретически могут извлекать существенную пользу из среды, в которой они функционируют. В частности, работая в живой клетке, они могут получать от нее топливо, строительный материал. Они могут использовать естественную ДНК как внешний носитель информации. Соответственно они могут считывать эту информацию или инициировать на основе этой информации синтез каких-либо полезных молекул или других роботов.

Вопрос о том, как и почему движется человеческое тело, с древнейших времен привлекал большое внимание исследователей. В результате сформировалась отдельная область знания, называемая теория действия. Хотя базовая идея теории действия была изложена еще Аристотелем (см. [131]), она сохранила свою актуальность и в наши дни (см., например, [132]). Более того, область ее применения существенно расширилась в связи с появлением различных робототехнических устройств (см., например, [133], [134]). Суть этой идеи наиболее ярко отражена в вопросе Витгенштейна (см. [135]):


“What is left over if I subtract the fact that my arm goes up from the fact that I raise my arm?”


Этот вопрос приводит к идее разделения собственно перемещения и того, что побуждает к этому перемещению. Нас могут интересовать самые различные изменения систем. Например, в случае человека это могут быть загар, покраснение или перемещения внутренних органов. В случае роботов – включение – выключение лампочки, изменение магнитного поля или давления масла и т.д. Учитывая то, что интересующее нас «движение», вообще говоря, не обязано быть чисто механическим или, будучи механическим, может быть не связано с изменением положения системы в пространстве, наиболее естественным представляется подход, основанный на описании «перемещений» при помощи абстрактных состояний. При этом мы полагаем, что система может принимать конечное множество


a[1], a[2], … , a[m]


абстрактных состояний. Соответственно, движение – это изменение состояния системы.

Вопросы, связанные с формализацией побуждения к движению, представляются наиболее трудными и интригующими. Попытки формализации побуждения существенно зависят от рассматриваемой системы. Однако для всех систем можно выделить две основные составляющие: механизм принятия решения и множество


b[1], b[2], … , b[k]


управляющих последовательностей. При этом мы полагаем, что любой переход из одного состояния в другое может быть описан при помощи некоторой управляющей последовательности. В этом случае в рамках теории действий управляющие последовательности обычно называются действиями. При рассмотрении теории действия для человека основной интерес представляет изучение механизма принятия решения. Это связано с тем, что существенная часть проблем моделирования уже решена Природой. В частности, исследователю не надо конструировать ни систему состояний, ни систему действий. Не надо задумываться и над тем, где и как хранить правила взаимодействия состояний и действий. В случае же робототехнических систем разработку модели движения приходится начинать с «чистого листа». При построении моделей динамических систем, описывающих действия, осуществляемые системами, общий подход основан на рассмотрении эволюции состояния системы в зависимости от действий. Соответственно базовой проблемой моделирования движения робототехнических систем является создание модели описания взаимодействия состояний и действий. В том случае, когда у нас есть полная информация об изменении системы в зависимости от осуществляемых действий, эта информация может быть представлена как ориентированный граф с взвешенными дугами, вершинами которого являются состояния системы, а весами – действия. При этом сами дуги отражают изменение состояний в зависимости от действий. Эта модель достаточно удобна в применении, хотя и требует слишком больших затрат памяти. Например, у робота KAMRO (Karlsruhe Autonomous Mobile Robot) (см., например, [136] – [140]), разработанного Institute for Real-Time Computer Systems and Robotics (IPR), конструкция состоит из мобильной платформы, двух манипуляторов и нескольких сенсоров. Учитывая то, что количество состояний этого робота сравнительно мало, для управления этим роботом можно безболезненно пользоваться графом действий. У гуманоидного робота Nao AI-05, созданного в 2005 году Aldebaran Robotics, двадцать пять степеней свободы [141]. Робот Honda Humanoid Robot, созданный Honda Corporation, имеет тридцать степеней свободы [142], [143]. Даже такое небольшое количество степеней свободы, как отмечено, например, в [144], приводит к весьма значительному количеству состояний O(2³⁰) и существенно затрудняет использование теоретико-графовой модели теории действий. Эта проблема приобретает катострофический размах при переходе на наноуровень. Особенно в случае ДНК. Рассмотрим, например, две молекулы ДНК одинаковой длины n, одна из которых целиком состоит из нуклеотидов A, а другая – из нуклеотидов T. Только различные варианты образования комплементарных связей A – T обеспечат этой системе из двух молекул существенно больше O(2ⁿ) состояний. С учетом того, что даже у уже существующих ДНК наномеханических роботов количество нуклеотидов в одной молекуле может превышать 10⁹, а количество самих молекул может быть более 10¹², количество состояний ДНК наномеханических роботов может быть больше экспоненты от 10²¹. Совершенно ясно, что построение теоретико-графовой модели теории действий для таких роботов абсолютно невозможно. Другой подход к моделированию теории действий для роботов основан на рассмотрении логических теорий, описывающих правила изменения состояний в зависимости от действий (см., например, [145], [146]). Использование динамических логик позволяет существенно снизить затраты памяти. Однако такой подход нередко приводит к значительному повышению вычислительной сложности решаемых проблем (см., например, [147]), что тоже неприемлемо. Довольно часто существенно снизить вычислительную нагрузку позволяет переход от моделирования состояний всей роботизированной системы к моделированию отдельных узлов. Например, рассмотрим робот видеонаблюдения. Пусть V – робот, состоящий из двух камер, способных работать в единственном режиме съемки. При этом камеры могут независимо друг от друга выполнять команды поворота по часовой стрелке вокруг своей оси на фиксированный угол. Первая камера может выполнять только команду p[1], предписывающую поворот на угол 2π / m для некоторой натуральной константы m. Соответственно вторая камера может выполнять только команду p[2], предписывающую поворот на угол 2 π / n для некоторой натуральной константы n. Выберем для каждой из камер некоторое положение в качестве положения с нулевым углом поворота. Из определения робота V очевидным образом следует, что его состояние полностью определяется парой углов поворота камер (φ,ψ), где


φ = 2jπ / m, 0 ≤ j ≤ m-1,


ψ = 2jπ / m, 0 ≤ j ≤ n-1.


Множество команд, которые может выполнять робот, имеет вид


{ (p[1],1), (p[1],p[2]), (1,p[2]) },


где команда (p[1],p[2]) требует поворота обеих камер, а команды (p[1],1) и (1,p[2]) – только первой и только второй, соответственно. Таким образом, теоретико-графовая модель для этого робота представляет собой граф, имеющий mn вершин, из каждой из которых выходит три ребра, взвешенных командами


(p[1],1), (p[1],p[2]), (1,p[2]),


соответственно. Легко понять, что вместо этого графа можно рассмотреть два графа, каждый из которых представляет одну камеру как самостоятельное устройство. Эти графы будут иметь m и n вершин, соответственно. Следовательно, мы получим квадратичное уменьшение модели. Легко понять, что при увеличении количества камер мы получим экспоненциальную экономию от числа камер. Однако подобная экономия возможна далеко не всегда, поскольку переход к моделированию отдельных узлов требует наличия у роботизированной системы независимых узлов. Например, система из двух манипуляторов, способных передавать друг другу предметы, не может быть разделена на два узла, поскольку при передаче предмета необходимо взаимодействие обоих манипуляторов. Более того, даже если отдельные части робота не вступают в непосредственный контакт, разделение может оказаться невозможным (например, роботизированная система может потерять равновесие и т.д.).

В качестве разумного компромисса между теоретико-графовым подходом и подходом, основанным на использовании динамических логик, в этой работе мы рассмотрим алгебраический подход к описанию изменения состояния системы в зависимости от действий.

Произвольный робот R можно рассматривать как некоторую конечную систему узлов


A[1], A[2], … , A[n]


доступных для управления. При этом каждый из узлов A[i] может принимать конечное множество состояний


a[i,1], a[i,2], … , a[i,p[i]].


Совокупность состояний отдельных узлов


a[1,j[1]], a[2,j[2]], … , a[n,j[n]]


в некоторый момент времени полностью определяет состояние всего робота в этот момент времени. Соответственно, для того чтобы изменить состояние робота, необходимо изменить состояния некоторых из его узлов.

Без ограничения общности можно предполагать, что каждый из узлов управляется конечной системой команд. При этом системы команд различных узлов не пересекаются.

Пусть система команд узла A[i] имеет вид


b[i,1], b[i,2], … , b[i,q[i]].


Для удобства мы будем полагать, что


b[i,1]=1


для любого i. При этом единичную команду мы будем рассматривать как отсутствие команды. Совокупность команд отдельных узлов


b[1,j[1]], b[2,j[2]], … , b[n,j[n]]


в некоторый момент времени полностью определяет действие в этот момент времени.

Рассмотрим полугруппу с внешне присоединенным нулем, порожденную множеством элементов


Ʃ = Φ  Ψ,


где


Φ = Φ[1]  …  Φ[n],


Φ[i] = { a[i,j] : 1 ≤ j ≤ p[i] },


Ψ = Ψ[1]  …  Ψ[n],


Ψ[i] = { b[i,j] : 1 ≤ j ≤ q[i] },


и заданную множеством определяющих соотношений Q[0], где


Q[0] = Q[0,1]  Q[0,2]  Q[0,3]  Q[0,4]  Q[0,5],


Q[0,1] = { a[i,j]a[s,t] = a[s,t]a[i,j] :


1 ≤ i ≤ n, 1 ≤ s ≤ n,


1 ≤ j ≤ p[i],


1 ≤ t ≤ p[s] },


Q[0,2] = { b[i,j]b[s,t] = b[s,t]b[i,j] :


1 ≤ i ≤ n, 1 ≤ s ≤ n,


i  s,


1 ≤ j ≤ q[i], 1 ≤ t ≤ q[s] },


Q[0,3] = { a[i,s]b[j,t] = b[j,t]a[i,s] :


1 ≤ i ≤ n,


1 ≤ j ≤ n,


i  j,


1 ≤ s ≤ p[i],


1 ≤ t ≤ q[j] } ,


Q[0,4] = { a[i,s]a[i,t] =0 :


1 ≤ i ≤ n,


1 ≤ s ≤ p[i],


1 ≤ t ≤ p[i] },


Q[0,5] = { b[i,t]a[i,s] = 0 :


1 ≤ i ≤ n,


1 ≤ s ≤ p[i],


1 ≤ t ≤ q[i] }.


Эту полугруппу мы будем называть базовой полугруппой робота R и обозначать S(R). Полугруппа S(R) при помощи своего множества определяющих соотношений задает пространство действий робота R. В дальнейшем для нас будут также представлять интерес фактор-полугруппы полугруппы S(R), задаваемые в ней системой определяющих соотношений Q, где


Q = Q[0]  Q[1]  Q[2]  Q[3]  Q[4],


Q[1]  { a[i,s]b[i,j] = a[i,t] :


1 ≤ i ≤ n,


1 ≤ s ≤ p[i],


1 ≤ t ≤ p[i],


1 ≤ j ≤ q[i] },


Q[2]  { aa[i,s]b[i,j] = aa[i,t] :


1 ≤ i ≤ n,


1 ≤ s ≤ p[i],


1 ≤ t ≤ p[i],


1 ≤ j ≤ q[i],


a  Φ⁺ },


Q[3]  { a[i[1],s[1]]b[i[1],j[1]]a[i[2],s[2]]b[i[2],j[2]] … a[i[r],s[r]]b[i[r],j[r]] =


a[i[1],t[1]]a[i[2],t[2]] … a[i[r],t[r]] :


1 ≤ i[1] < i[2] < … < i[r] ≤ n,


1 ≤ s[1] ≤ p[i[1]], 1 ≤ s[2] ≤ p[i[2]], … , 1 ≤ s[r] ≤ p[i[r]],


1 ≤ t[1] ≤ p[i[1]], 1 ≤ t[2] ≤ p[i[2]], … , 1 ≤ t[r] ≤ p[i[r]],


1 ≤ j[1] ≤ q[i[1]], 1 ≤ j[2] ≤ q[i[2]], … , 1 ≤ j[r] ≤ q[i[r]] },


Q[4]  { aa[i[1],s[1]]b[i[1],j[1]]a[i[2],s[2]]b[i[2],j[2]] … a[i[r],s[r]]b[i[r],j[r]] =


aa[i[1],t[1]]a[i[2],t[2]] … a[i[r],t[r]] :


1 ≤ i[1] < i[2] < … < i[r] ≤ n,


r < n,


1 ≤ s[1] ≤ p[i[1]], 1 ≤ s[2] ≤ p[i[2]], … , 1 ≤ s[r] ≤ p[i[r]],


1 ≤ t[1] ≤ p[i[1]], 1 ≤ t[2] ≤ p[i[2]], … , 1 ≤ t[r] ≤ p[i[r]],


1 ≤ j[1] ≤ q[i[1]], 1 ≤ j[2] ≤ q[i[2]], … , 1 ≤ j[r] ≤ q[i[r]],


a  ((Φ[1]  …  Φ[n] ) \ (Φ[i[1]]  …  Φ[i[r]]))⁺ } .


Множество Q[1] определяет изменения состояний узлов робота, не зависящие от текущих состояний других узлов. Множество Q[2] задает изменения состояний узлов, которые возможны лишь в том случае, когда некоторые другие узлы находятся в подходящих состояниях. Системы Q[3] и Q[4] определяют изменения состояний узлов, которые должны происходить синхронно. При этом множество Q[3] задает синхронные изменения состояний узлов робота, не зависящие от текущих состояний других узлов. Соответственно множество Q[4] задает синхронные изменения состояний узлов, которые возможны лишь в том случае, когда некоторые другие узлы находятся в подходящих состояниях. Несложно проверить, что если для некоторого i, 1 ≤ i ≤ n, слово w  Ʃ⁺ содержит более одного вхождения букв из множества Φ[i], то в полугруппе S(R) слово w равно нулю. Кроме того, произвольное слово w  Ʃ⁺ в полугруппе S(R) представимо в виде


x[1]x[2] … x[n]  1,


где для любого i имеет место соотношение x[i]  ( Φ[i] Ψ[i] )*. Отсюда вытекает, что произвольный элемент w полугруппы S(R) равен нулю или слову вида


x[1]x[2] … x[n],


где


x[1]x[2] … x[n]  1,


x[i] = y[i]z[i],


y[i]  { 1 } Φ[i],


z[i]  Ψ[i]*.


Такое представление элементов полугруппы S(R) будем называть каноническим. Для произвольной полугруппы S(R) по произвольному представлению элемента его каноническое представление может быть эффективно построено за полиномиальное время. Канонические представления ненулевых элементов полугруппы S(R) находятся во взаимно однозначном соответствии с парами всевозможных состояний робота R и потенциально применимых программ. Фактор-полугруппы полугруппы S(R), получаемые добавлением некоторого множества определяющих соотношений Q, определяют пространство состояний – действий робота R.

Следует отметить, что в худшем случае полугрупповая модель не дает преимущества по сравнению с графовой. Однако для того, чтобы достигнуть худшего случая необходимо, чтобы у робота все степени свободы во всех состояниях зависели друг от друга. Поскольку для ДНК характерно то, что подавляющее большинство взаимодействий определяется лишь несколькими соседними нуклеотидами, для ДНК наномеханических устройств полугрупповая модель сочетает компактность динамических логик и вычислительную эффективность графовых моделей.

В рамках только что рассмотренной модели применительно к ДНК наномеханическим устройствам попарное различие узлов A[1], A[2], … , A[n] и систем команд b[i,1], b[i,2], … , b[i,q[i]] обусловлено необходимостью обозначить позиции нуклеотидов в устройстве, к которым применяются действия. Однако поскольку количество типов нуклеотидов ограничено, в любом достаточно большом устройстве нуклеотиды одного и того же типа должны повторяться многократно в различных местах. Поэтому многие команды, различающиеся в модели, будут совпадать на физическом уровне. Следовательно, имеет смысл рассмотреть соответствие между множеством формальных программ F и множеством реальных команд E, выполняемых на физическом уровне. Будем говорить, что элемент x из F находится в отношении ρ с элементом y из E, если модельная команда x кодирует команду y. Рассмотрим частично упорядоченные множества (P(F),) и (P(E),) всех подмножеств множеств Fи E, соответственно. Это множества всех формальных программ и всех программ физического уровня. Бинарный контекст (см. [148]) (F,E,ρ) индуцирует соответствие Галуа (f,g) между множествами (P(F),) и (P(E),), задаваемое отображениями


f : X  _xX { y : y  F, x ρ y },


g : Y  _yY { x : x  E, x ρ y }.


Соответствие Галуа (f,g) индуцирует оператор замыкания


h = g  f


на множестве (P(F),) (см. [149]):


X  h(X);


X  Y  h(X)  h(Y);


h(h(X)) = h(X).


Пусть L – множество всех элементов (X,Y) из декартова произведения (P(F),) и (P(E),) таких, что h(X) = X и f(X) = Y. На множестве L рассмотрим бинарное отношение , задаваемое соотношением


(X[1],Y[1])  (X[2],Y[2])  X[1]  X[2].


Пара (L,) является полной решеткой и называется решеткой Галуа бинарного контекста (F,E,ρ) (см. [150]). Решетка Галуа задает сжимающее отображение множества (P(F),) на (P(E),).

Применение моделей и алгоритмов классической робототехники дает возможность проводить тестирование отдельных элементов наносистем на макроуровне. В частности, для структурного моделирования нанорешеток и наноустройств могут быть эффективно применены результаты исследований по разработке моделей и алгоритмов для метаморфных (metamorphic) или самореконфигурующихся (self-reconfigurable) роботов (см. [151] – [166]). Для исследования алгоритмов управления движением наномеханических роботов представляют существенный интерес также алгоритмы неголономного управления движением роботов (см. [167] – [185]) и алгоритмы вероятностного управления движением роботов (см. [186] – [204]).

Совершенно естественно, что для ДНК наномеханических устройств пригодны многие идеи, модели и алгоритмы, разрабатываемые и применяемые для нанороботов в целом. В частности, ведутся исследования в области автоматического планирования (см., например, [205] – [209]), моделирования представления знаний (см., например, [210] – [212]), разработки систем управления механическим движением (см., например, [213] – [220]), создания графических симуляторов (см., например, [221] – [225]).