TY - JOUR

T1 - Интервальные временные ограничения для планирования согласованных движений многозвенных манипуляторов

AU - Яковлев, Константин Сергеевич

AU - Зайцев, Андрей Сергеевич

N1 - Зайцев А.С., Яковлев К.С. Интервальные временные ограничения для планирования согласованных движений многозвенных манипуляторов // Информатика и автоматизация. 2025. № 4 (24). C. 1007-1028.

PY - 2025/8/19

Y1 - 2025/8/19

N2 - В работе рассматривается задача планирования согласованных движений для системы многозвенных роботов-манипуляторов. Одним из перспективных современных подходов к её решению является конфликтно-ориентированное планирование, позволяющее отказаться от построения комбинированного пространства поиска высокой размерности за счет перехода к последовательному решению совокупности задач более низкой размерности. Этот переход осуществляется путем задания пространственно-временных ограничений при наличии конфликта в индивидуальных планах манипуляторов и последующего перепланирования с учетом наложенных ограничений. К сожалению, известные к настоящему моменту способы наложения ограничений оперируют отдельными моментами времени, что снижает их эффективность на практике. В данной работе представляется новый алгоритм конфликтно-ориентированного планирования, основанный не на точечных, а на интервальных временных ограничениях – GECBS-T. С теоретической точки зрения, предлагаемый алгоритм гарантирует ограниченную суб-оптимальность конструируемых решений, т.е. при любом наперёд заданном пользователем ограничении w >1, стоимость решения GECBS-T не будет превышать стоимость оптимального решения более, чем в w раз. На практике же, предлагаемый алгоритм существенно превосходит аналогичные алгоритмы по скорости решения задач планирования, что подтверждается проведенными экспериментами в робототехническом симуляторе mujoco, включающими2-4 робота-манипулятора Kuka с 7 степенями свободы каждый.

AB - В работе рассматривается задача планирования согласованных движений для системы многозвенных роботов-манипуляторов. Одним из перспективных современных подходов к её решению является конфликтно-ориентированное планирование, позволяющее отказаться от построения комбинированного пространства поиска высокой размерности за счет перехода к последовательному решению совокупности задач более низкой размерности. Этот переход осуществляется путем задания пространственно-временных ограничений при наличии конфликта в индивидуальных планах манипуляторов и последующего перепланирования с учетом наложенных ограничений. К сожалению, известные к настоящему моменту способы наложения ограничений оперируют отдельными моментами времени, что снижает их эффективность на практике. В данной работе представляется новый алгоритм конфликтно-ориентированного планирования, основанный не на точечных, а на интервальных временных ограничениях – GECBS-T. С теоретической точки зрения, предлагаемый алгоритм гарантирует ограниченную суб-оптимальность конструируемых решений, т.е. при любом наперёд заданном пользователем ограничении w >1, стоимость решения GECBS-T не будет превышать стоимость оптимального решения более, чем в w раз. На практике же, предлагаемый алгоритм существенно превосходит аналогичные алгоритмы по скорости решения задач планирования, что подтверждается проведенными экспериментами в робототехническом симуляторе mujoco, включающими2-4 робота-манипулятора Kuka с 7 степенями свободы каждый.

KW - планирование движения

KW - планирование траекторий

KW - многоагентное планирование

KW - манипулятор

KW - конфликтно-ориентированное планирование

KW - поиск на основе конфликтов

KW - поиск по графу

KW - нтервальные ограничения

KW - временные ограничения

KW - CBS

KW - M-RAMP

KW - conflict-based

KW - constraints

KW - graph search

KW - manipulators

KW - motion planning

KW - multi-agent

KW - search-based

KW - time range

UR - https://www.mendeley.com/catalogue/7d755c6e-f7a3-38e9-b45f-893bd77e90b7/

U2 - 10.15622/ia.24.4.1

DO - 10.15622/ia.24.4.1

M3 - статья

VL - 24

SP - 1007

EP - 1028

JO - SPIIRAS Proceedings

JF - SPIIRAS Proceedings

SN - 2078-9181

IS - 4

ER -