Robots in Space multiagent problem: information and cryptographic aspects.pdf Распределённая система -это группа децентрализованных взаимодействующихисполнителей [1]. Распределённый алгоритм - это протокол работы и взаимодействияисполнителей в распределённой системе, превращающий децентрализованную группув коллектив, совместно решающий некоторую задачу [2]. Параметрический алгоритм(или протокол) - это масштабируемый алгоритм для исполнителя в распределённойсистеме (протокол распределённой системы соответственно), в котором множество ис-полнителей в системе использовано как константа-параметр.Мультиагентная система -это распределённая система, состоящая из аген-тов [3]. Агент -это автономный (воспринимающий мир разделённым на себя и сре-ду, включающую всё остальное), реагирующий (способный взаимодействовать со сре-дой и отвечать на воздействия среды) объект (в объектно-ориентированном смысле),внутреннее состояние которого можно характеризовать в терминах мнений или веры(Believes), целей (Desires) и намерений (Intentions) агента. Мультиагентный алго-ритм - это распределённый алгоритм для мультиагентной системы. Анонимный про-токол - это протокол мультиагентной системы, одинаковый для всех агентов.В работе исследуется следующая задача о роботах в пространстве (RinS - Robotin Space). В евклидовом пространстве (k ^ 2) находятся n > 1 автономных робо-тов и столько же укрытий в общем положении (т. е. никакие три объекта не лежатна одной прямой). Местоположение всех укрытий фиксировано и известно каждомуроботу. Каждому роботу изначально назначено индивидуальное укрытие, о которомробот знает. Каждый робот знает свои координаты в пространстве, знает о существо-вании всех остальных роботов, но не знает их координаты, и знает, что всем роботамизначально назначены и известны индивидуальные укрытия. В некоторый момент вре-мени все роботы останавливаются, фиксируют свои текущие позиции, и затем они вседолжны выбрать укрытия, чтобы двинуться к ним по прямолинейному маршруту.Ясно, что роботам нельзя сталкиваться. Роботы могут взаимодействовать каждыйс каждым попарно, вести переговоры в парах и обмениваться укрытиями. Задача:разработать анонимный параметрический мультиагентный алгоритм переговоров, га-рантирующий, что каждый робот когда-нибудь будет точно знать, что его маршрутк укрытию, которое он выбрал в результате переговоров, не пересекается и никогдане будет пересекаться с маршрутами остальных роботов. Эта задача «выросла» из ра-нее рассмотренной задачи о роботах на Марсе (Mars Robot Puzzle - MRP) [4]: MRPявляется частным случаем RinS на плоскости.хРабота выполнена в рамках проекта СО РАН 15/10 на 2012-14 гг.Протоколом распределения укрытий будем называть любой мультиагентный алго-ритм, решающий задачу RinS. Такой протокол может состоять из алгоритма перего-воров для индивидуальных роботов и алгоритма-планировщика общения между робо-тами мультиагентной системы. Будем говорить, что алгоритм-планировщик общениямежду роботами удовлетворяет условию справедливости, если в любой момент време-ни для любого робота, желающего контактировать в этот момент с каким-либо другимроботом-партнёром, обязательно наступит в будущем момент времени, когда партнёрбудет готов к общению с данным роботом. Варианты алгоритма-планировщика можнонайти в работе [4].Щелчок - это алгоритм переговоров между двумя роботами, который позволяетэтим роботам проверить, нужно ли им обмениваться укрытиями, и удовлетворяет сле-дующим двум условиям:- если текущие пути роботов пересекаются, то они должны совершить обмен;- после обмена укрытиями суммарная длина путей строго уменьшается.Два крайних случая щелчка - это простой щелчок, при котором обмен укрытиямивыполняется тогда и только тогда, когда пути пересекаются, и щелчком со сравнением,при котором обмен укрытиями выполняется тогда и только тогда, когда сумма длинпутей уменьшается. В рамках данного исследования неважно, как именно устроенщелчок, но существенно то, что при исполнении этого протокола роботы сообщаютдруг другу что-либо о своём положении.В работе [4] поставлен вопрос об оценке сложности алгоритмов назначения укры-тий, основанных на щелчках. Сейчас мы готовы дать очень простой ответ на этотвопрос.Теорема 1. Любой алгоритм назначения укрытий, основанный на протоколещелчка, не может совершить более --- n щелчков, где L и l - максимальное иминимальное расстояния между роботом и укрытием в системе, а А - минимальныйдекремент суммы длин путей при щелчке (который не равен 0, так как никакие триобъекта не лежат на одной прямой).Сужением протокола распределения укрытий на множество S будем называть про-токол, отличающийся только тем, что входные данные для него (положения роботови укрытий) должны принадлежать множеству S.В рамках исследования информационного аспекта задачи RinS в качестве вход-ных данных рассматриваются действительные числа. При этом неважно, как роботыхранят их в памяти; будем интересоваться общим количеством битов (сообщений),переданных участниками друг другу в ходе исполнения протокола. Будем называтьпротокол финитным, если при любых допустимых значениях входных данных егоработа завершается после передачи конечного количества битов.Теорема 2. Существует финитный параметрический анонимный мультиагент-ный алгоритм распределения укрытий, основанный на протоколе щелчка и справед-ливом планировщике общения между агентами.Будем называть протокол ограниченным, если существует такая константа N, чтопри любых допустимых значениях входных данных его работа завершается после пе-редачи не более N битов. Будем называть протокол ограниченным по сообщениям,если существует такая константа N, что при любых допустимых значениях входныхданных его работа завершается после передачи не более N сообщений.Теорема 3. Пусть бесконечное множество точек S С , k ^ 2, лежащих в об-щем положении, обладает следующим свойством: существует непрерывная замкнутаяплоская кривая, содержащая S и ограничивающая выпуклое плоское множество. То-гда сужение любого протокола распределения укрытий между n ^ 2 участниками намножество S не может быть ограниченным. Кроме того, если множество S более чемсчётно, то сужение любого протокола распределения укрытий между n ^ 2 участни-ками на множество S не может быть ограниченным по сообщениям.В рамках исследования криптографического аспекта задачи RinS будем считать,что входные данные (координаты роботов и укрытий) берутся из некоторого конечногомножества точек в пространстве , k ^ 2, все координаты которых - числа, заданныеконечным числом разрядов в какой-либо (фиксированной) позиционной системе счис-ления. Заметим, что в этом случае смысл протокола распределения укрытий состоитв вычислении некоторой функции координат роботов и укрытий, значением которойявляется искомое распределение. В силу теоремы о конфиденциальных вычислениях(Oblivious Transfersecure multi-party computation) [5, 6] существует способ вычисленияэтой функции, при котором участники не получат никаких дополнительных сведенийо входных данных друг друга.Теорема 4. Пусть S С - произвольное конечное множество точек, все коорди-наты которых - числа с фиксированным числом разрядов в некоторой фиксированнойпозиционной системе счисления. Тогда1) существует сужение на множество S основанного на простом щелчке прото-кола распределения укрытий, в котором агенты не сообщают друг другу своикоординаты;2) существует сужение на множество S основанного на щелчке со сравнениямипротокола распределения укрытий, в котором агенты не сообщают друг другусвои расстояния до укрытий.

Скачать электронную версию публикации