Temporal Reasoning with Kinodynamic Networks


  • Han Zhang University of Southern California
  • Neelesh Tiruviluamala University of Southern California
  • Sven Koenig University of Southern California
  • T. K. Satish Kumar University of Southern California




Plan And Schedule Execution, Monitoring And Repair


Temporal reasoning is central to Artificial Intelligence (AI) and many of its applications. However, the existing algorithmic frameworks for temporal reasoning are not expressive enough to be applicable to robots with complex kinodynamic constraints typically described using differential equations. For example, while minimum and maximum velocity constraints can be encoded in Simple Temporal Networks (STNs), higher-order kinodynamic constraints cannot be represented in existing frameworks. In this paper, we present a novel framework for temporal reasoning called Kinodynamic Networks (KDNs). KDNs combine elements of existing temporal reasoning frameworks with the idea of Bernstein polynomials. The velocity profiles of robots are represented using Bernstein polynomials; and dynamic constraints on these velocity profiles can be converted to linear constraints on the to-be-determined coefficients of their Bernstein polynomials. We study KDNs for their attractive theoretical properties and apply them to the Multi-Agent Path Finding (MAPF) problem with higher-order kinodynamic constraints. We show that our approach is not only scalable but also yields smooth velocity profiles for all robots that can be executed by their controllers.




How to Cite

Zhang, H., Tiruviluamala, N., Koenig, S., & Kumar, T. K. S. (2021). Temporal Reasoning with Kinodynamic Networks. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 415-425. https://doi.org/10.1609/icaps.v31i1.15987