Abstract
Learning latent costs of transitions on graphs from trajectories demonstrations under various contextual features is challenging but useful for path planning. Yet, existing methods either oversimplify cost assumptions or scale poorly with the number of observed trajectories. This paper introduces DataSP, a differentiable all-to-all shortest path algorithm to facilitate learning latent costs from trajectories. It allows to learn from a large number of trajectories in each learning step without additional computation. Complex latent cost functions from contextual features can be represented in the algorithm through a neural network approximation. We further propose a method to sample paths from DataSP in order to reconstruct/mimic observed paths' distributions. We prove that the inferred distribution follows the maximum entropy principle. We show that DataSP outperforms state-of-the-art differentiable combinatorial solver and classical machine learning approaches in predicting paths on graphs.
Abstract (translated)
学习从轨迹演示中观察到的转移的潜在成本是具有挑战性的,但有助于路径规划。然而,现有的方法要么过于简化成本假设,要么在观察到的轨迹数量上表现不佳。本文介绍了DataSP,一种不同可微的 all-to-all 短路径算法,以促进从轨迹中学习潜在成本。它允许在每次学习步骤中从大量轨迹中学习,而无需额外计算。通过神经网络近似的复杂上下文特征可以表示算法的潜在成本函数。我们进一步提出了一种从DataSP中采样路径的方法,以重构/模仿观察到的路径分布。我们证明了推断的分布符合最大熵原理。我们证明了DataSP在预测 graphs上的路径方面优于最先进的差分组合算法和经典机器学习方法。
URL
https://arxiv.org/abs/2405.04923
