Поиск еды ..., Муравьи Опции

[renesko1]

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

Сам вопрос, какой алгоритм поиска пищи у насекомых или какие нибудь идеи.? Я искал про муравьев, но увы не нашел,
хотя искал не очень долго. У меня есть пару мыслей : к примеру помечать клетки, где мы оно было и если встретили их идти от них до стены... бррррр бред.Ведь насекомые вроде не дигаются спиралью от центра норки ?
ps
Самое главное, что оно слепое, и без обояния. но с памятью на команды.

[hardcase]

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

Сообщение отредактировано: hardcase - 14.05.2008 12:52

[Lapp]

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

Насколько я понял, речь шла не о нахождении оптимального решения, а о моделировании поведения. Генетический метод пригоден, скорее, для GPS - просчитываются тысячи вариантов и выбирается один. Муравью (как, впрочем, и человеку) такой метод не годится: он один, он не может испробовать все пути своими ногами. Кроме того, если даже он и начал это делать - зачем ему продолжать, когда он нашел еду в первом проходе, пусть и неоптимальном?

renesko1, мне кажется, зря ты его ослепил и лишил обоняния. Такой муравей выживет только купаясь в питательном растворе.. И то ему лучше все же уметь искать концентрацию побольше. Ну, не амеба же он! Да и амеба имеет некоторые зачатки ощущений. Это, мне кажется, основа разумной организации чего бы то ни было. Система: сигнал с сенсора - обработка данных - принятие решения. Без этого вряд ли можно получить приемлемую модель.

[andriano]

Честно говоря, не совсем понятна цель данного мероприятия.
Если с целью поэкспериментировать с алгоритмом поведения, то целесообразно, навыерное, сделать основную программу, служащую для управления , инициализации и визуализации, к которой подключать dll-ку, где, собственно, и описывать поведение. Желательно предусмотреть несколько муравьев с несколькими dll-ками и смотреть, кто их них выживет.
Но в целом я согласен с Lapp: возможности муравья слишком сильно урезаны, чтобы можно было надеяться получить что-нибудь интересное.

[klem4]

Я бы сделал муравью всетаки область видимости/унюхиваемости например относительно муравья на n клеток вверх вниз влево и вправо (фактически квадрат n*n), а из этой области уже выбирал бы клетку с едой к которой нужно отправиться и съесть ее, можно выбирать например самую ближнюю или случайно выбранную или еще как-нибудь, в случае если в области видимости нету еды, то совершить рандомный шаг в любую соседню клетку.

[andriano]

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

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

[renesko1]

Графически я реализовал в первую очередь, опирясь на советы к теме fool. Действительно, так гораздо легче
отлаживать и етстировать и ... много еще.
Я думаю тогда реализую муравья как обьект с методами(вспомнил : птицы летают, но пингвин тоже птица),
пока для начала он у меня запись.
А насчет чувств я тоже думал о 1клеточных, как сапожок реагирует на свет , зря я его так( но интересно
можно ли как нибудь без них. )
Думаю сделать сначало "зрение" , а потом нюх. Хотя в био. было наоборот(кажется). Если все получится можно будет скомбинировать на дальних растояниях нюх, потом зрение.
andriano мог бы чуть подробние про :

Код

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

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

Сообщение отредактировано: renesko1 - 14.05.2008 21:41

[andriano]

renesko1, ты задавай конкретные вопросы, иначе непонятно, что именно подробнее.
Насчет пули - не знаю, я имел в виду нормальное распределение.
Генетический алгоритм, думаю, здесь если и пытаться использовать, то лишь на ГОРАЗДО более поздних стадиях, когда уже сложится впечатление, что следует задавать на входе, и чего ожидать на выходе.

[renesko1]

Ясно. Я про "распределение по Гауссу с дисперсией". Можешь в 2 словах, если не сложно.
Что именн представляет данный метод ? И где еще можно его использовать ?
http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%...%BD%D0%B8%D0%B5 это то ?
а то мне не очень понятно. Хотя бы на бытовом уровне.
А про пулю вот http://ru.wikipedia.org/wiki/%D0%9F%D1%83%...%81%D1%81%D0%B0

[andriano]

Ну, примерно так:
1. Задаешься радиусом видимости (для примера 3 клетки в каждую сторону).
2. Задаешься, во сколько раз радиус "унюхиваемости" больше радиуса видимости (например, в 2.5-3 раза).
3. Вычисляешь СКО (в данном случае 8 клеток).
4. Делаешь для распределения массив весов:
4.1. Заводишь двумерный массив по 3 СКО в каждую сторону от середины, т.е. 49х49 (3*8 + 1 + 3*8).
4.2. Вычисляешь интеграл для каждой ячейки по формуле в зависимости от радиуса (расстояния до центральной ячейки).
4.3. При необходимости - нормируешь, но, думаю, в данном случае не нужно.
5. Массив весов готов.

Для вычисления потенциала:
1. Заводишь вспомогательное поле размером равное полю, по которому будут бродить муравьи (вещ.тип).
2. Перед началом вычисления очищаешь поле (обнуляешь).
3. Пробегаешь по всем клеткам основного поля. Если есть еда, то прибавляешь к полю потенциала вспомогательное поле, отцентрировав его по рассматриваемой ячейке, и домножив на количество еды.
4. В полученном поле находишь градиент в тех точках, где расположены муравьи. В принципе, для оптимизации можно и потенциал вычислять только в окрестностях этих точек (+/- одна ячейка).

Для пояснения приведу одномерный пример.
Пусть у нас Гаусс: 0 1 2 5 2 1 0
Пусть поле имеет ширину 10 клеток и в нем в точке 4 расположено 2 ед. еды, а в точке 8 - 3 единицы.
Обнуляем: 0 0 0 0 0 0 0 0 0 0
От 4-й точки: 0 0 2 4 10 4 2 0 0 0
От 8-й точки: 0 0 0 0 0 0 3 6 15 6
Суммируем: 0 0 2 4 10 4 5 6 15 6

[renesko1]

Те берем и делаем квадрат 3*3(пример) центр 3 переферия 2.
В центре 2 ед. еды. --> центр 6. Переферия 4.
В движение чувствуем 4. От нее находим 6. И Находим еду.
Следовательно я делаю 3 карты. 1 визуальная + движение.
2 для обояния. 3 зрение.
Мур. обзаведется направлением головы (для зрения)
И 3 командами: шаг вперед, поворот влево/вправо.
Andriano , спасибо хорошо обьясняешь.

[andriano]

Не совсем понял, что ты собираешься делать.
Карты, думаю, достаточно одной, просто в каждой ее ячейке будет структура, например:
- количество еды,
- проходимо или нет,
- потенциал еды (для обоняния),
- что-то еще.
Не понял, что значит "В движение чувствуем 4. От нее находим 6"
Мы анализируем потенциал в точке, где находится муравей и соседних с ней. По этим точкам находим градиент - т.е. с какой стороны сильнее всего пахнет едой.
Зрение может быть либо секторным (с учетом поворота головы), либо круговым (без учета).
На основе как зрительной, так и обонятельной информации принимаем решение, куда двигаться. Если зрение секторное, то на основе обоняния также принимаем решение о повороте головы. Кстати, у муравья, IMHO, длолжна быть локальная память. Т.е. хотя поворот головы и занимает некоторое время (кстати, это имее смысл только в условиях конкуренции), он помнит то, что видел раньше. Т.е. это еще один массив.
Насчет сооотношения между СКО и радиусом видимости я уже говорил раньше - это чтобы еду можно было почуять, пока она еще не видна.

[renesko1]

Со структурой ты здорово придумал. Зрение секторное. Обояние круговое. R(нюха) > r(зрения)

Код

Не понял, что значит "В движение чувствуем 4. От нее находим 6"

В смысле находим клетку где "сила запаха "= n потом клетку где сила запаха m (m>n) и тд до визуального контакта.
Еще раз спасибо. Я просто медленно печатую, и мысли нализают одна на другую и выходит каламбур(в плохом смысле слова). В целом я понял. К сожалению буду делать где то через неделю (экзамены).

[andriano]

Что значит "находим"?
"Находим" - это один шаг или цепочка шагов. Если один - то неправильно. Градиент задает направление и, если мы ориентируемся на запах, то двигаемся в этом направлении. Но лучше сперва повернуть голову и посмотреть.