Численно устойчивый решатель задач линейного комплементарного программирования для моделирования контактирующих составных абсолютно твёрдых тел

В статье представлен численно устойчивый алгоритм решения задач линейного комплементарного программирования (LCP), применяемый для моделирования контактов с трением между составными абсолютно твёрдыми телами, каждое из которых представлено произвольным полигональным объектом. Сначала выявлены две проблемы популярного решателя задач LCP на основе метода поворота, известного как алгоритм Лемке, и его расширения с лексикографическим упорядочиванием; эти проблемы обусловлены численными ошибками, особенно в случае плохо обусловленных задач LCP. Предложенный алгоритм устраняет указанные проблемы, сохраняя все кандидаты на поворот и осуществляя поиск последовательности поворотов, приводящей к решению. Формулировка контактной динамики на основе LCP объединяется с алгоритмом прямой динамики составных абсолютно твёрдых тел, что позволяет выполнять всё моделирование с использованием подхода динамического программирования. Результаты моделирования с гуманоидным роботом показывают, что алгоритм Лемке — как с лексикографическим упорядочиванием, так и без него — не способен решать сложные контактные задачи, тогда как предложенный алгоритм успешно моделирует такие ситуации. Также показано, что результаты моделирования качественно сходны с результатами экспериментов на аппаратном прототипе.