GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (5)След. > >>   Поиск:  
 Автор Тема: Формализация среды для задачи "Двухуровневое целепологание"
tac
Сообщений: 2601
Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 1:02
Все же я решил завести отдельную тему, которая я надеюсь поможет объединить усилия по формализации, предложенной мной задачи.
Начальное описание и обсуждение было здесь: http://forum.membrana.ru/forum/scitech.html?parent=1053142741&page=0

Вторым шагом было понимание того, что среду нужно целиком отделить и исследовать вне контекста применяемых методов. Это позволит затем предоставить среду (возможно в неком алгоритмическом представлении, например, на С#) для желающих опробывать свои методы и таким образом организовать некий турнир программистов, что в свою очередь наверняка побудит к размышлениям, сопоставлению методов и идей.

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

Так, как есть и другие подходы, задачи и среды - авторы которых не смотря на формально разные приследуемые цели, тем ни менее работают в близких направлениях, то обсуждение шло в разных местах:
http://www.gotai.net/forum/Default.aspx?postid=10428#10428
http://www.gotai.net/forum/Default.aspx?postid=10949#10949
http://www.gotai.net/forum/Default.aspx?postid=10697#10697

возможно имеет смысл сделать одну площадку для дискуссий ...
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 1:20
О среде:

I. Формализация моно, мульти агентности ...

Несмотря на то, что в среде "Civilization" находится только один игрок (в дальнейшем агент), следует отметить две особенности приводящие к тому, что данную среду нужно рассматривать как среду с мульти-агентными взаимодействиями:
1. Агент с помощью юнитов - поселенцев за один ход параллельно в разных местах воздействует на среду;
2. Воздействие каждого юнита-поселенца сводятся (кроме движения необходимого для этого) к созданию активного центра (юнита-город) в среде. Такой город в течении времени способен воздействовать на среду и возможности агента в целом, а так же поощрения от среды, независимо от последующих действий агента. Такие воздействия могут быть трех типов: (1) уменьшаю число территории для будующей застройки, обесценивая соответствующую территорию (2) накопляют ресурсы, т.е. изменяют поощрение (3) увеличивают число поселенцев, что позволяет агенту увеличивать параллельность своих действий .

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

II. Формализация поощрений:

Для агента существует следующая информация, которая может быть расцененна как поощрение:

1. Прирост (изменение) показателей Ri в городе Nj,
где i=1 (кол-во пищи), 2 (кол-во металла), 3 (кол-во денег),
4 (кол-во укомплектованных городом рабочих),
5 (кол-во укомплектованных городом поселенцев);
j - порядковый номер города.
2. Прирост (изменение) суммарных показателей Sum(Ri).

III. Зависимости переходов из состояния в состояние (модель переходов)



Здесь
- i-ое действие j-ого юнита-поселенец;
- i-ое действие j-ого юнита-рабочий (в городе находятся 9 рабочих);


IV. Модель действий - А, B

1. Для юнита-поселенец, возможны 9 действий: Аi={"(1,1)","(0,1)","(1,0)","(-1,1)","(1,-1)","(0,-1)","(-1,0)","(-1,-1)","0,0"}, где передвижения обозначены приращением координат переселенца, при этом если юнит остается на месте, то это означает что он - строит город.

2. Для юнита-рабочий, возможны 2 действия Bi={0,1}: работать, отдыхать.

3. Действие агента - суммарное действие всех переселенцев А1*А2*...*Аn.

4. Действие города Сi={ 0, 1 }: 0 - накапливать ресурсы, 1 - обменять ресурсы на юнит-поселенец.


Управление 9-ю действиями юнита-поселенец осуществляет агент.
Управление 2-мя действиями юнита-рабочий и 2-мя действиями города осуществляет среда по определенным правилам.

V. Определение состояний - S

Состояние зависит от:
1. Размера карты на плоскости (в рассматриваемом случае 15*10+14*9 = 276 квадратов)
2. От количества городов. Эквивалентом этому будет замена одного города 9 рабочими, которые находятся на площади города, и находятся в одном из двух состояний работают/отдыхают
3. От количество одновременно перемещающихся юнитов-поселенец.

Общее число состояний равно:
1. Если имеется только один юнит поселенец и нету городов, то число состояний равно размеру карты, т.е. 276 состояний, обозначим это число N;
2. Если на карте нету юнитов поселенец и могут быть созданы различные города, то число состояний равно , т.к. на каждом квадрате карты может быть рабочий который работает или отдыхает, и соответственно число состояний будет равно комбинации всех возможных случаев. Величина достаточно большая чтобы выразить число возможных ситуаций цифрой, поэтому более уместно использовать размер требуемый для хранения этого числа, т.е. 276 бит (35 байт), и в дальшейшем выражать число состояний в битах.
3. Если на карте неограниченное число юнитов поселенец и нету городов, то , где M - максимальное число юнитов в одной клетке, ограничим такое максимальное число юнитов, которые могут находится в одной клетке 8-ю, тогда необходимо 276 байт.
4. Если имеется различное число юнитов поселенец и могут быть созданы различные города, то число состояний равно сумме (или комбинации ???, но вроде указанного объема достаточно, чтобы состояния описывались в указанном объеме независимо друг от друга, т.е. отдельно наличие городов и отдельно наличие поселенцов) пунктов 2 и 3, т.е. 276+35 = 311 байт



(в последнем пункте не уверен, поэтому перепроверте, кто соображает ... )

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

VI. Модель наблюдения (необходимо для задач PoMDP) - О

1. Для юнита-поселенец для наблюдения доступны 25 состояний (квадратов на карте) в 8 из которых он может переместиться.
2. Для агента видна та часть карты, которая была открыта юнитами-поселенцами за время игры
3. Модель наблюдений лучше описать графом из 276 вершин, соответствующим каждому квадрату карты, и 8 переходами от каждой вершины - показывающими взаимное расположение квадратов на карте. При этом общая модель наблюдений будет следующей
, т.е. 1 - соответствующий квадрат на карте открыт (доступен для наблюдения), 0 - информация о квадрате не известна.


----
Об агенте:

A.I. Контроллер пространственных ходов - врожденный безусловный минимальный интеллект агента

Контроллер пространственных ходов обеспечивает минимальный рациональный уровень ходов юнитов-поселенцев. Для того, чтобы интеллектуальная часть агента не была загруженна малозначищими вопросами. Для этого эта интеллектуальная часть должна оценить возможность каждого из 10 действий (а не выбрать одно из них) и предоставить эту оценку (число от 0 до 255) контроллеру пространтвенных ходов (КПХ).

1. КПХ осуществляет то действие, которое оценивается максимальной оценкой.
2. Если юнит достиг границы карты, и действие с максимальной оценкой нельзя осуществить будет выбранно действие с меньшей оценкой пока действие будет возможно осуществить.
3. Если юнит совершает перемещение обратное по направлению к предыдущему действию, то такое действие отклоняется и осуществляется действие с меньшей оценкой.
4. Если юнит хочет совершить действие по созданию города и оценка этого действия не превышает 100, то такое действие отклоняется и осуществляется действие с меньшей оценкой.
5. Если все оставшиеся возможные действия оценены одинаково, то осуществляется движение в случайном направлении.


A.II. Учитель - врожденный условный минимальный интеллект агента

Если действия КПХ агент не может изменить, то обучение учителя (которое происходит в off line фазе) он может со временем изменить. Обучение учителя направленно на то, чтобы агент мог хоть как то рационально вести себя в среде. Такое рациональное поведение может оказаться выгодным при равномерном распределеннии ресурсов по территории карты, а так же при примерно одинаковой важности каждого из ресурсов. Это происходит от того, что учитель обучает агента оценивать каждое из 9 действий (кроме отдыха) в соответствии с методом взвешенной оценки альтернатив.
А именно, из 9 альтернатив по каждому ресурсу находится максимальное и минимальное значение ресурсов суммированное по все площади города. Значения всех ресурсов приводятся к одному маштабу
, где maxmin - разница между максимумом и минимумом среди 9 альтернатив данного ресурса. Полученные значения и есть оценки.

А. III. Упрощение задачи, для акцентирования на нерешенной проблеме

Изначальная задача была упрощенна с целью сосредоточить внимание на основной проблеме. В изначальном варианте, предполагалась, что юниты обладают только визуальными сенсорами, на которые подается визуальное изображение 25 квадратов карты, т.е. модель наблюдения для юнитов-поселенец. И учитель дополнительно обучает распозновать эти территории. При этом одна и таже территория могла иметь разное изображение. В текущей версии, это положение упрощенно так, что уже на вход подается тип территории, а учитель обучает только тому сколько на ней ресурсов и как оценить совокупность из 25 территорий. При этом этим упрощением не стоит злоупотреблять в реализации агента. Предполагается, что агент будет способен построить модель реализуемых им действий и стратегий в целом, имея возможно прогнозировать в неизвестных ситуациях. Но упрощение позволяет сосредоточится не на прогнозировании вида территорий (на основе изображения), а именно на всем ходе принятия решений по оценке действия.
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 1:40
Пояснения по поводу моно-мульти агентности

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

Пояснения по поводу поощрения:

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

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

Но в случае не известных условий и/или большом числе видов территорий задача стоновится NP-полная. И поэтому анализ прямых зависимостей между местоположением города и ростом показателей не является решением проблемы (из-за множественности и недостаточности стабильности взаимосвязей). Поэтому требуется как раз избежать детального анализа и выработать тактические (локальные) приемы, которые будут полезны, т.е. в итоге не сильно отличаться от результатов полноценного анализа (в случае когда это возможно). Это в свою очередь позволит сформулировать стратегию на базе локальных тактик в условиях когда всестороний и полноценный анализ причино-следственных зависимостей не возможен.


[Ответ][Цитата]
daner
Сообщений: 4204
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 1:43
"Правильной дорожкой идете, товарищи!" (с)В.Ленин
Вот только не надо перемешивать описание среды с целями и пожеланиями
это я про объяснения о кооперации и подобном.

Одно замечание и одно дополнение (важное)

Замечание: Города не меняют поощрение, они меняют кол-во ресурсов Утилиту Агента если хотите. Поощрение скорее меняет само появление города (если я правильно понимаю).

Дополнение. Важной особенностью игры является изменяемое кол-во агентов. Хотя, я бы все-таки говорил о каком-то конечном числе агентов (как игроков, так и городов), просто пока агента нет, он считается не активным и постоянно применяет одно и тоже действие "пропускаю ход". Что-то в этом роде. Так много проще для анализа.
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:02
Цитата:
Автор: daner
Замечание: Города не меняют поощрение, они меняют кол-во ресурсов Утилиту Агента если хотите. Поощрение скорее меняет само появление города (если я правильно понимаю).


Не совсем понял, а наверное, вы писали, до того как я уточнил про поощрения, т.к. рост количества ресурсов - это и есть одно из поощрений ... а вот просто появление города поощрение ни как не затрагивает, иначе агент только бы и стремился бы строить города без разницы где ..
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:14
Цитата:
Автор: daner
Дополнение. Важной особенностью игры является изменяемое кол-во агентов. Хотя, я бы все-таки говорил о каком-то конечном числе агентов (как игроков, так и городов), просто пока агента нет, он считается не активным и постоянно применяет одно и тоже действие "пропускаю ход". Что-то в этом роде. Так много проще для анализа.


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

Не знаю, чем это проще для анализа ... но можно, конечно, при необходимости сделать такое предположение. Тогда можно упростить т.к. потенциальных 9 рабочих - это и есть город для которых можно ввести действия "работаю/отдыхаю", и добавим двигающегося поселенца с его 10 действиями (8 перемещений/строю город/отдыхаю) ... Ограничить можно: 100 поселенцев и 900 рабочих, которые с избытком покрывают всю территорию в 300 квадратов (только для активных рабочих запрещается находится на одном квадрате, а остальные могут быть на одном квадрате, да и еще город на городе построить нельзя).
Что от такого упрощения можно выйграть ?
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:22
Цитата:
Автор: daner
Вот только не надо перемешивать описание среды с целями и пожеланиями
это я про объяснения о кооперации и подобном.


Ну, давайте отделим одно от другого, мне порой сложно это сделать, не потеряв важной идеи при описании среды. Т.к. форум позволяет редактировать сообщения, скажите мне что можно отнести однозначно к целям, пожеланиям, а что собственно оставить в формализации среды. Например, давайте второй пост оставим только для описания формализации (с целями), а третий для пояснений с пожеланиями.
[Ответ][Цитата]
daner
Сообщений: 4204
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:36
Цитата:
Автор: tac
Не совсем понял, а наверное, вы писали, до того как я уточнил про поощрения, т.к. рост количества ресурсов - это и есть одно из поощрений ... а вот просто появление города поощрение ни как не затрагивает, иначе агент только бы и стремился бы строить города без разницы где ..

Да я писал это до предыдущего поста. Но как бы там ни было, я имел ввиду небольшое уточнение. Город производить за ход ... скажем 1$... т.е. каждый ход получаем константное кол-во денег. Т.е. город не меняет поощрение за ход. Что его меняет? Появление города. скажем было 2 города и получали по 2 монеты за ход, построили еще город, и получаем 3 монеты за ход... т.е. изменение. Я вот это имел ввиду.
[Ответ][Цитата]
daner
Сообщений: 4204
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:39
Цитата:
Автор: tac

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

Не знаю, чем это проще для анализа ... но можно, конечно, при необходимости сделать такое предположение. Тогда можно упростить т.к. потенциальных 9 рабочих - это и есть город для которых можно ввести действия "работаю/отдыхаю", и добавим двигающегося поселенца с его 10 действиями (8 перемещений/строю город/отдыхаю) ... Ограничить можно: 100 поселенцев и 900 рабочих, которые с избытком покрывают всю территорию в 300 квадратов (только для активных рабочих запрещается находится на одном квадрате, а остальные могут быть на одном квадрате, да и еще город на городе построить нельзя).
Что от такого упрощения можно выйграть ?


Нда... несколько сложновато получается. Я забыл про условие, что игроки не должны быть на одном поле. ладно это пока не важно. дальше сами увидите, что будет проще: дополнительные условия или не постоянное кол-во агентов (я пока не знаю что сказать).
[Ответ][Цитата]
daner
Сообщений: 4204
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:44
Цитата:
Автор: tac
Ну, давайте отделим одно от другого, мне порой сложно это сделать, не потеряв важной идеи при описании среды. Т.к. форум позволяет редактировать сообщения, скажите мне что можно отнести однозначно к целям, пожеланиям, а что собственно оставить в формализации среды. Например, давайте второй пост оставим только для описания формализации (с целями), а третий для пояснений с пожеланиями.

Ну это надо снова все перечитывать... просто описывайте саму среду, без замечаний как она на агента влиять будет и что агенту для этого надо делать. Например то что города и игроки не соперничают -- это замечание о среде, а вот про создание коалиций... Их кто должен создавать? "город"? Нет. Их будут только игроки создавать, поэтому к среде это не относиться. То же и с последним предложением третьего поста.
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:44
Цитата:
Автор: daner
Да я писал это до предыдущего поста. Но как бы там ни было, я имел ввиду небольшое уточнение. Город производить за ход ... скажем 1$... т.е. каждый ход получаем константное кол-во денег. Т.е. город не меняет поощрение за ход. Что его меняет? Появление города. скажем было 2 города и получали по 2 монеты за ход, построили еще город, и получаем 3 монеты за ход... т.е. изменение. Я вот это имел ввиду.


А теперь, понял ... честно говоря, я долго сомневался, что является поощрением константное кол-во денег увеличивающиеся на каждом ходу, или их прирост-изменение (т.е. скорость) ... судя по всему прирост ... И не только денег, но и всех показателей (см. выше) ... Более общим наверное будет считать, что появление новых рабочих дает прирост ряда показателей, а при появлении города просто появляются два рабочих, а затем по мере роста пищи появляются дополнительные рабочии (хотя могу и уменьшаться) ...
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:51
Цитата:
Автор: daner
Ну это надо снова все перечитывать...


Вы, все же обращайте переодически внимание на 2-ой, 3-ий пост, я постараюсь их держать в соответствии с тем, что удалось достичь путем обсуждений, чтобы все было в одном месте, и не приходилось перечитывать весь ход обсуждений.
[Ответ][Цитата]
daner
Сообщений: 4204
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 03 сен 08 2:55
Цитата:
Автор: tac
А теперь, понял ... честно говоря, я долго сомневался, что является поощрением константное кол-во денег увеличивающиеся на каждом ходу, или их прирост-изменение (т.е. скорость) ... судя по всему прирост ... И не только денег, но и всех показателей (см. выше) ... Более общим наверное будет считать, что появление новых рабочих дает прирост ряда показателей, а при появлении города просто появляются два рабочих, а затем по мере роста пищи появляются дополнительные рабочии (хотя могу и уменьшаться) ...

Ну наверное. Вам виднее.
[Ответ][Цитата]
tac
Сообщений: 2601
На: Формализация среды для задачи "Двухуровневое целепологание"
Добавлено: 04 сен 08 8:52
Во второй пост добавил ряд уточнений, особенно актуально подсчет общего числа состояний в задаче - попробывал определить, но хотелось бы, чтобы кто нибудь верифицировал ...
[Ответ][Цитата]
Trilobite
Сообщений: 201
За чистоту терминов!
Добавлено: 04 сен 08 15:00
Не хотелось бы, как говорится, гасить энтузиазм,
но формализация задачи и ее обсуждение как-то стороной обошли вопросы:
а) а среда ли это вообще?
б) и есть ли тут агент?

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

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

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

Для сравнения возьмем шахматы.
Здесь доска является средой скорее для шахматных фигур и пешек, но не для шахматиста.
Для последнего она только один из объектов его окружения, пусть и ключевой.
Шахматист играет роль агента в другом мире - мире соперников, тренера, шахматной литературы и регулярных турниров. И надо понимать, что воспитать гроссмейстера без всего этого крайне затруднительно.
[Ответ][Цитата]
 Стр.1 (5): [1]  2  3  4  5След. > >>