Propagating Piecewise-Linear Weights in Temporal Networks


  • Luke Hunsberger Vassar College
  • Roberto Posenato Université degli Studi di Verona



This paper presents a novel technique using piecewise-linear functions (PLFs) as weights on edges in the graphs of two kinds of temporal networks to solve several previously open problems. Generalizing constraint-propagation rules to accommodate PLF weights requires implementing a small handful of functions. Most problems are solved by inserting one or more edges with an initial weight of δ (a variable), then using the modified rules to propagate the PLF weights. For one kind of network, a new set of propagation rules is introduced to avoid a non-termination issue that arises when propagating PLF weights. The paper also presents two new results for determining the tightest horizon that can be imposed while preserving a network’s dynamic consistency/controllability.




How to Cite

Hunsberger, L., & Posenato, R. (2021). Propagating Piecewise-Linear Weights in Temporal Networks. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 223-231.