{ (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]
181
доступных для управления. При этом каждый из узлов 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]]
в некоторый момент времени полностью определяет действие в этот момент времени.
Рассмотрим полугруппу с внешне присоединенным нулем, порожденную множеством элементов
182
Ʃ = Φ Ψ,
где
Φ = Φ[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,
183
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] }.
184
Эту полугруппу мы будем называть базовой полугруппой робота 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]] =
185