/robotic-sorting

Primary LanguageHTMLMIT LicenseMIT

Моделирование роботизированного сортировочного центра

Основные предположения

В пункты получения сортировочного логистического центра непрерывно поступают посылки, которые роботы должны сортировать - развести в соответствующие пункты назначения центра.

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

Роботы могут двигаться вперед и поворачиваться в одном из 4 направлений. Роботы выполняют действия по командам системы управления за различные, заданные моделью, дискретные времена:

  • бездействие (время задается системой управления)
  • движение на одну клетку вперед
  • поворот на 90 градусов
  • взятие посылки (в пункте получения)
  • сдача посылки (в пункте назначения)

В момент получения посылки роботом, случайным образом выбирается её пункт назначения - куда нужно отвести.

Столкновением роботов считается одновременное использование одной клетки двумя роботами:

  • находятся в одной клетке
  • движутся в одну клетку
  • один движется в клетку, в которой находится другой
  • один движется в клетку, откуда движется другой

Установка

  1. предполагается, что уже установлены:

    • python 3.12
    • simpy (библиотека python)

  2. перейти в нужную директорию, например в домашнюю:

     cd ~

  3. склонировать репозиторий:

     git clone https://github.com/juk-r/robotic-sorting.git

  4. добавить в PYTHONPATH, например для linux:

     export PYTHONPATH="${PYTHONPATH}:~/robotic-sorting"

  5. запустить пример:

     python robotic-sorting -map "robotic-sorting/data/small_map.json" -type "robotic-sorting/data/example/robot-type.json" -position "robotic-sorting/data/example/position.json" -distribution "robotic-sorting/data/example/distribution.json" -algorithm "robotic-sorting/brains/random_brain.py" -mode run -time 1000

  6. проверить, что в консоль выведено количество посылок: 11

Запуск

Запуск производится командой следующего вида (из директории содержащей robotic-sorting):

python robotic-sorting -map FILE -type FILE -position FILE -distribution FILE -algorithm FILE -mode {run,record,average} -time TIME [-output OUTPUT] [-count COUNT]

с параметрами:

  1. -map - файл конфигурации карты
  2. -type - файл конфигурации типа роботов, времен действий
  3. -position - файл конфигурации расположения роботов
  4. -distribution - файл конфигурации распределения вероятности
  5. -algorithm - файл алгоритма
  6. -time - модельное время, которое будет работать модель
  7. -mode - тип запуска
    • run - выводит количество доставленных посылок
    • record - выводит все действия роботов в формате csv, рекомендуется указывать файл вывода
    • average - выводит количество доставленных посылок и стандартное отклонение при указанном количестве запусков
  8. -output - файл в который выводится результат, по умолчанию выводится в стандартный stdout
  9. -count - количество запусков для типа average

Конфигурация модели

Конфигурация задается несколькими .json файлами и выбранным алгоритмом. Запуск производится из консоли.

Карта склада

Конфигурация склада задается файлом .json, соответствующим схеме, содержит:

  • span - расстояние между клетками
  • cells - прямоугольный двумерный массив клеток (1 координата - строка сверху вниз, 2 координата - столбец слева направо), каждая из которых содержит необязательные:
    • free - может ли робот находиться, по умолчанию может: true
    • inputId - уникальный номер пункта получения, по умолчанию его нет
    • outputId - уникальный номер пункта назначения, по умолчанию его нет

Можно посмотреть пример карты.

Свойства роботов

Конфигурация задается файлом .json, соответствующим схеме, содержит:

  • timeToMove - время для движения вперед на 1 клетку
  • timeToTurn- время для поворота на 90 градусов
  • timeToTake - время, чтобы взять посылку
  • timeToPut - время, чтобы положить посылку

Можно посмотреть пример.

Расположение роботов

Конфигурация задается файлом .json, соответствующим схеме, содержит:

  • robots - список, элементы которого содержат:
    • id - необязательный id
    • x - позиция по 1 координате, считая с 0
    • y - позиция по 2 координате, считая с 0
    • direction - направление одно из:
      • up - вверх
      • left - влево
      • down - вниз
      • right - вправо

Можно посмотреть пример.

Распределение вероятностей назначений

Для каждого пункта получения определяется распределение вероятностей пунктов назначений для поступающих посылок файлом .json, соответствующим схеме, содержит:

  • distribution объект, в котором:
    • ключ - уникальный номер пункта получения или "other" для всех незаданных
    • значение "uniform" - равномерное распределение
    • значение - объект:
      • ключ - уникальный номер пункта назначения или "other", тогда у незаданных пунктов назначений будет равномерное распределение
      • значение - вероятность это пункта назначения

Можно посмотреть пример распределения.

Архитектура моделирования

Модель разделена на 2 части: сменная система управления и модель (управляемого) склада.

До запуска, модель склада:

  1. считывает файлы конфигурации,
  2. расставляет роботов и уведомляет о каждом систему управления,
  3. запрашивает у системы управления первое действие для каждого робота,

Во время исполнения, модель повторяет следующее:

  1. проверяет возможность выполнения полученного действия робота.
  2. если возможно, выполняет действие робота
  3. если действие не может быть выполнено, возникает ошибка или оповещается система управление в зависимости от вида ошибки,
  4. когда действие закончилось, запрашивает следующее действие у системы управления,

Когда моделирование закончено, то есть прошло заданное время или доставлено заданное количество посылок, модель склада выводит требуемые результаты.

Модель управляемого склада

Конструкция модели склада

  • /brains/ - алгоритмы управления
  • /mail_factories/ - генераторы посылок
  • /maps/ - карты, основная и дополнительные которые хранят дополнительную информацию
  • /mail_factories/ - генераторы посылок для пунктов получения.
  • /structures.py - неизменяемые структуры данных
  • /modelling.py - основной класс Model, связывающий остальные классы и получающий управление после получения команды моделирования.
  • /brains/brain.py - абстрактный класс Brain, описывающий интерфейс системы управления.
  • /maps/map.py - карта склада Map хранит статическую информацию.
  • /cell.py - класс Cell, реализующий клетку карты
  • /robot.py - робот Robot, выполняющий действия.

До запуска

  1. Для каждого робота модель резервирует клетку, соответствующую начальному положению.
  2. Для каждого робота модель вызывает Brain.new_robot.
  3. Для каждого робота модель узнает первое действие: вызывает Brain.get_next_action.

Запуск хода модельного времени

Производится вызовом методов класса Model:

  • run_for_time - для моделирования в течении заданного времени
  • run_for_mails - для моделирования заданного количество посылок

Во время исполнения

После того, как модель получило очередное действие очередного робота, она выполняет это действие следующим образом:

  • бездействовать: модель добавляет событие, что робот закончит действие через заданное время
  • двигаться: модель резервирует следующую клетку, добавляет событие через нужное для перемещения время, отменяет резервирование предыдущей клетки.
    • если следующей клетки не существует, возникает исключение PositionOutOfMap
    • если данное действие приведет к столкновению, то оно не выполняется и вызывается метод системы управления collision_callback, затем заново get_next_action.
  • повернуть: добавляет событие через нужное для поворота время.
  • взять: модель пытается забрать посылку, вызывая Cell.get_input и добавляет событие через нужное для получения время.
    • если у робота уже есть посылка, возникает DoubleMailTake
    • если клетка не является пунктом получения, возникает NotInputCell.
  • положить: модель пытается положить посылку и добавляет событие через нужное для сдачи время.
    • если у робота нет посылки, возникает MailToPutAbsence
    • если направление посылки не совпадает с пунктом назначения или клетка не является пунктом назначения, возникает IncorrectOutput.

После обработки очередного действия очередного робота, модель узнает для этого робота новое действие, вызывая Brain.get_next_action.

Модель системы управления

Интерфейс

Модель системы управления необходимо реализовать на python специальным классом, который наследуется от класса Brain и состоит из методов:

  • new_robot(Robot), вызывается моделью склада для каждого добавленного робота до запуска модели.
  • get_next_action(Robot) -> Robot.Action | (Robot.Action.idle, int), вызывается моделью склада для каждого робота, метод возвращает предстоящее (одно из 5) действие для данного робота.
    • Для бездействия, возвращается дополнительный параметр - время бездействия.
  • collision_callback(Robot) -> None, вызывается моделью склада, если полученное действие не может быть выполнено. Не обязательный метод, если метод не представлен, то действие, приводящее к столкновению, вызывает исключение.

В файле .py, содержащем выбранный алгоритм, должен быть один и только один класс, наследованный от Brain.

Информация о состоянии модели склада

Модель система управления может получить всю информацию о текущем состоянии модели склада из поля _model (экземпляр класса Model), которое содержится в классе Brain.

Класс Model содержит неизменяемую часть - карта склада - поле map (экземпляр класса Map), и переменною - состояние роботов - поле robots (список роботов - экземпляры класса Robot).

Карта склада может быть получена из полей карты Map:

  • inputs - список координат пунктов получения
  • outputs - список координат пунктов назначение
  • inputs_ids - список id пунктов получение
  • outputs_ids - список id пунктов назначения
  • height, width - размеры карты по x и y
  • метод has(Position)->bool - проверка существования клетки с заданной координатой
  • метод [Position] (индекс) - получить клетку (экземпляр класса Cell).

Каждая клетка содержит неизменяемые поля:

  • free (bool) - может ли робот находиться на ней
  • input_id (int) - id пункта получения или None, если нет
  • output_id (int) - id пункта назначения или None, если нет
  • reserved (bool) - какой-то робот зарезервировал клетку - использует, другие не могут в нее перемещаться.

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

  • id (str | None) - id робота, заданный конфигурацией. Если не задан, то будет None
  • type RobotType - тип робота, информация о свойствах робота:
    • type.time_to_move (int) - время, чтобы проехать 1 клетку
    • type.time_to_turn (int) - время, чтобы повернуть на 90 градусов
    • type.time_to_take (int) - время, чтобы взять посылку
    • type.time_to_put (int) - время, чтобы положить одну посылку

Поскольку переменная часть модели состоит только из состояния роботов, то о текущем состоянии модели склада можно узнать из полей класса Robot. (Список всех роботов находится в self._model.robots):

  • position.x, position.y - целые координаты клетки, на которой находится робот (начиная с 0)
  • direction одно из 4 направление (Direction)
  • mail (Mail) - посылка, которую везет робот или None, если нет посылки:
    • mail.id (int)- уникальный номер посылки
    • mail.destination (int) - направление, в которое нужно доставить