Структура данных для времен, когда позиция была занята, с быстрым способом изменить это время - PullRequest
Новая
       73

Структура данных для времен, когда позиция была занята, с быстрым способом изменить это время

1 голос
/ 02 мая 2020

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

Я думал о такой хеш-таблице: 

position_hash[position].append((agent_id, time)) # every entry is a list

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

offset_hash[agent_id].append((time_where_offset_is_applied, offset_value))

наконец я бы проверил, есть ли столкновение, посмотрев на время. вот так: 

times = [values[1] for values in position_hash[current_position]]
agents = [values[0] for values in position_hash[current_position]]
times_with_offset = times
for agent_index, agent in enumerate(agents):
    for offset_times, offset_values in offset_hash[agent]:
        if offset_times <= times[agent_index]:
            times_with_offset[agent_index] += offset_values
collisions = [
    abs(current_time - time) <= 2 for agent, time in enumerate(times_with_offset) if agent != current_agent
]
if any(collisions):
   # add new collision here

Лично я чувствую, что это выглядит немного неуклюже. Есть ли лучший, быстрый или простой способ добиться того, что было описано?

Редактировать 2 - Простой пример и дополнительная информация:

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

Карта

Прописные буквы - это блоки, а нижний регистр - цель 

+++++++++++
+       + +
+    0 1+a+
+ +++++++A+
+         +
+B+++++++ +
+b+       +
+ +   +++++
+++++++++++

Решения с одним агентом

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

[[(2, 5)], [(2, 4)], [(2, 3)], [(2, 2)], [(2, 1)], [(3, 1)], [(4, 1)], [(4, 2)], [(4, 3)], [(4, 4)], [(4, 5)], [(4, 6)], [(4, 7)], [(4, 8)], [(4, 9)], [(3, 9), (2, 9)]]

[[(2, 7)], [(2, 6)], [(2, 5)], [(2, 4)], [(2, 3)], [(2, 2)], [(2, 1)], [(3, 1)], [(4, 1)], [(5, 1), (6, 1)]]

Сгенерированное poition_ha sh

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

{(3, 9): [('red', 0), (0, 15)], (5, 1): [('green', 0), (1, 9)], (2, 5): [(0, 0), (1, 2)], (2, 4): [(0, 1), (1, 3)], (2, 3): [(0, 2), (1, 4)], (2, 2): [(0, 3), (1, 5)], (2, 1): [(0, 4), (1, 6)], (3, 1): [(0, 5), (1, 7)], (4, 1): [(0, 6), (1, 8)], (4, 2): [(0, 7)], (4, 3): [(0, 8)], (4, 4): [(0, 9)], (4, 5): [(0, 10)], (4, 6): [(0, 11)], (4, 7): [(0, 12)], (4, 8): [(0, 13)], (4, 9): [(0, 14)], (2, 9): [(0, 15)], (2, 7): [(1, 0)], (2, 6): [(1, 1)], (6, 1): [(1, 9)]}

Редактировать 1 : опечатка в коде

Редактировать 2 : добавлено больше информация

...