2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение21.01.2012, 23:48 
Раздела кибернетика не нашел, поэтому постчу здесь.

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

И, может, кто литературу на эту тему подскажет?

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение22.01.2012, 10:31 
Аватара пользователя
Мне кажется, в классическом случае это следует из эквивалентности клеточных автоматов и машины Тьюринга:
Цитата:
было доказано, что в «Жизни» существует универсальный конструктор (машина Тьюринга), а в 2002 году универсальный конструктор был построен.

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение23.01.2012, 19:46 
2_hum_
Цитата:
всякое ли поведение, которое можно реализовать через централизованное управление этими агентами, можно также реализовать и децентрализованно

Мне кажется, что ряд моментов сводится к вопросам надежности доставки сигналов в децентрализованной среде. Если сообщения могут перехватываться или портиться, то как известно (cf. парадокс двух генералов), это приводит к проблемам синхронизации работы отдельных частей такой сети. Также, в достаточно большой децентрализованной сети, за счет процессов самоорганизации, централизованность может появиться сама -- некоторые узлы могут координировать работу других.

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

2AlexDem
Цитата:
Мне кажется, в классическом случае это следует из эквивалентности клеточных автоматов и машины Тьюринга

Но не всякий набор правил приводит к такой вычислительной универсальности.

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение23.01.2012, 22:04 
2AlexDem
Спасибо. Кое-чего для себя почерпнул. Правда, так и не нашел, что имелось в виду под существованием универсального конструктора. А хотелось бы, если говорить в рамках теории клеточных автоматов, узнать следующее:
пусть $F$ клеточное поле размером $m\times  n$, в клетки которого помещены одинаковые конечные автоматы с состояниями из некоторого конечного множества $S$, воспринимающие текущие состояния своих ближайших соседей в качестве внешнего сигнала.
Вопрос:
для всяких ли функций $G: S^{m\times  n}\times  \mathbb{N} \rightarrow  S^{m\times  n}$ (здесь $S^{m\times  n}$ - множество матриц с элементами из $S$) существует такая конструкция конечного клеточного автомата, что для всякого набора начальных состояний $||s^0_{i,j}|| \in S^{m\times  n}$ этих конечных автоматов последовательность состояний $||s^t_{i,j}||, t = 1,2,...,$ проходимых автоматами во времени будут в точности соответствовать значениям $G\big(||s^0_{i,j}||, t\big), t = 1,2,...$.

Поле $F$ содержательно можно рассматривать как набор фиксированных мест в окрестностях перекрестка. Конечные автоматы - водители, которые могут обозревать только своих ближайших соседей. Их состояния "двигается", "стоит", "намеревается совершить маневр такой-то", "находится в конфликтной точке" и проч., проч. Вопрос, можно ли подобрать таким образом правила дорожного движения, чтобы обходясь без светофоров реализовать, например, поведение: если по главной дороге поток большой и со второстепенной выезд затруднен, то на главной дороге все останавливаются на некоторое время и пропускают некоторое количество машин со второстепенного направления.

В общем-то, вопрос вырос вот откуда: до появления светофоров порядок проезда определялся по общему правилу "помехи справа" (ну с доп. условием пропуска пешехода и рельсового транспорта). Вопрос: есть ли какая-то сущностная (неизбежная) необходимость появления светофоров, и если да, то в чем ее суть. В первую очередь бросается в глаза, что светофоры реализуют центральное управление (подача общей для всех информации). Значит, возможно, что именно тут "собака зарыта". Может быть, не всякое поведение можно организовать через (одни и те же для всех) предписания поведения в локальной ситуации (наподобие правила "помехи справа")?

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение25.01.2012, 10:40 
Аватара пользователя
_hum_ в сообщении #530506 писал(а):
Вопрос:
для всяких ли функций $G: S^{m\times n}\times \mathbb{N} \rightarrow S^{m\times n}$ (здесь $S^{m\times n}$ - множество матриц с элементами из $S$) существует такая конструкция конечного клеточного автомата, что для всякого набора начальных состояний $||s^0_{i,j}|| \in S^{m\times n}$ этих конечных автоматов последовательность состояний $||s^t_{i,j}||, t = 1,2,...,$ проходимых автоматами во времени будут в точности соответствовать значениям $G\big(||s^0_{i,j}||, t\big), t = 1,2,...$.

Ну вот если всё поле белое, а на следующем шаге на нём должна быть всего одна чёрная точка - как такое сделать, если окрестностью клетки не является всё поле? Локально такое не сделать - появятся ещё точки в независимых областях поля.

_hum_ в сообщении #530506 писал(а):
Правда, так и не нашел, что имелось в виду под существованием универсального конструктора

Я тоже не разбирался в деталях, но если клеточный автомат позволяет моделировать машину Тьюринга, то очевидно, что любой алгоритм для МТ можно переложить для КА, в том числе и тот, что осуществляет управление.

Circiter в сообщении #530451 писал(а):
Но не всякий набор правил приводит к такой вычислительной универсальности.

Это само собой...

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение25.01.2012, 22:02 
AlexDem в сообщении #530980 писал(а):
Ну вот если всё поле белое, а на следующем шаге на нём должна быть всего одна чёрная точка - как такое сделать, если окрестностью клетки не является всё поле? Локально такое не сделать - появятся ещё точки в независимых областях поля.

Согласен. Нужно какие-то ограничения ставить (учитывающие однородность поля; или избавляться от нее).
AlexDem в сообщении #530980 писал(а):
но если клеточный автомат позволяет моделировать машину Тьюринга,

Я что-то пропустил? Где говорилось, что он может моделировать машину Тьюринга? И под МТ понималась универсальная МТ или какая-то частная? Если последнее, то
AlexDem в сообщении #530980 писал(а):
то очевидно, что любой алгоритм для МТ можно переложить для КА, в том числе и тот, что осуществляет управление.

неверно. Класс МТ, моделируемых КА, может быть более узким, чем множество всех МТ.

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение29.01.2012, 14:24 
Аватара пользователя
см.: Гарднер М. Крестики - нолики. - М.: Мир, 1988. C. 338:
Цитата:
В февральском номере Scientific American за 1971 г. я поднял вопрос о том, позволяют ли правила игры "Жизнь" построить универсальную вычислительную машину, а уже в следующем номере сообщил читателям, что игра "Жизнь" в самом деле является универсальной. Дело в том, что независимо друг от друга Госпер в Массачусетсом технологическом институте и Конуэй в Кембридже "универсализировали" пространство игры "Жизнь", подтвердив возможность использования "глайдеров" в качестве носителей информации с целью моделирования машины Тьюринга.

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение29.01.2012, 17:29 
Аватара пользователя
Насколько я понимаю, теме топика посвящена книжка В.И. Варшавский, Д.А. Поспелов "Оркестр играет без дирижера"

 
 
 
 Re: Эквивалентны ли централизованное и децентрализованное упр-ие
Сообщение29.01.2012, 19:54 
AlexDem, спасибо, гляну.

Alik, спасибо, по-видимому, то, что нужно; бум читать (правда, год смущает - 1984 :) ).

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group