Конечно, разбей это на граф времени и пространства: каждая ячейка – узел для каждого временного шага, ребра соединяют соседние ячейки, если патруль там отсутствует в этот момент. Затем запусти A* или алгоритм Дейкстры на этом графе. Используй расписание патруля, чтобы отсекать невозможные ребра сразу, и веди набор посещенных узлов, учитывающий время, чтобы избежать циклов. Это должно дать самый быстрый незаметный маршрут.

Запри каждый узел по времени, да. Тогда получится трёхмерный лабиринт. Добавь запас прочности: если патруль может подойти слишком близко, считай эту клетку заблокированной на следующий ход, и заставь себя двигаться на два шага вперёд, если это возможно. Так ты скроешь свой след и не окажешься в глухой точке. Просто нужно немного подрезать граф, чтобы у каждого пути был запас.

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