Імовірнісні дорожні карти
У серпні 1996 року Кавракі й Латомб зі Стенфорда та Швестка й Овермарс з Утрехта опублікували в IEEE Transactions on Robotics and Automation (том 12, випуск 4, с. 566–580) метод планування руху з двох фаз: у фазі навчання випадково вибрані безколізійні конфігурації робота зʼєднуються простим швидким локальним планувальником у граф, дорожню карту; у фазі запиту початкова й кінцева конфігурації приєднуються до графа, і в ньому шукається шлях. Для плоских шарнірних роботів із багатьма ступенями свободи планування займає частку секунди на робочій станції близько 150 MIPS після кількох десятків секунд навчання.
Чому це важливо
Планування руху для тіл із багатьма ступенями свободи, яке точні методи робили практично неможливим через розмір простору конфігурацій, стало справою секунд: замість описувати вільний простір його вибірково пробують. На цьому стоїть планування для маніпуляторів і гуманоїдів наступних десятиліть.
За резюме, метод загальний і простий у реалізації, придатний практично для будь-якого голономного робота, потребує вибору кількох параметрів (наприклад, тривалості фази навчання), що залежать від сцени, але виявилися легкими у виборі, а ефективність можна підвищити, підлаштовуючи складники (наприклад, локальний планувальник) під конкретного робота. Запис стоїть на резюме, бо повний текст платний. Чого запис не стверджує: кількості ступенів свободи в дослідах, частки успішних запитів, розмірів дорожньої карти і будь-яких чисел, крім наведених.