Недоопределенные модели. О некоторых особенностях применения недоопределенных моделей в робототехнике

Метод недоопределенных моделей (Н-моделей) был предложен А. С. Нариньяни еще в начале 80-x годов и является весьма эффективной технологией решения задач удовлетворения ограничений в самой общей постановке [2]. В Н-моделях переменной сопоставляется недоопределенное значение (или Н-значение). Недоопределенное значение является промежуточным между полной определенностью (точное значение) и полной неопределенностью. В процессе вычислений Н-значение может становиться только более точным, гарантируя тем самым монотонность вывода.

Каждой переменной, участвующей в описании задачи, ставится в соответствие ее недоопределенное расширение (Н-расширение).

Недоопределенными расширениями могут быть точные значения, перечисление (множество подмножеств), множества, интервалы (для них характерна интервальная алгебра), мультиинтервалы и т. д.

Например, если универсум некоторой переменной есть множество целочисленных значений, то ее Н-расширением может быть полная неопределенность, перечисление, интервал или мультиинтервал.

Для вычисления Н-модели обобщенная вычислительная модель строится как четверка.

M = (V, W, C, R),.

где V — множество объектов из заданной предметной области, R — множество ограничений на значения объектов из V, W — множество функций присваивания (определяют новое значение объекта как функцию от текущего и присваиваемого значений), C — множество функций проверки корректности (определяют изменение значения объекта и проверяют правильность этого нового значения).

Каждому объекту v V сопоставлены универсум Xv и начальное значение из универсума, а также функция присваивания Wv и функция проверки корректности Cv.

Ограничения из R должны быть функционально интерпретируемыми, т. е. всякое отношение r(x₁,, x_n) должно быть представлено набором функций f_i (i=1,, n), вычисляющих значение каждой переменной из X' на основании заданных значений других переменных. Функция f_i называется функцией интерпретации отношения r, если.

x_i = f_i (x₁,, x_i-1, x_i+1,, x_n),.

Такие функционально интерпретируемые отношения и называются ограничениями.

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

Каждой объектной вершине сопоставляются тип и значение, а также функции присваивания и проверки корректности.

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

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

Рассмотрим далее возможные решения двух конкретных задач.