Fast (Incremental) Algorithms for Useful Classes of Simple Temporal Problems with Preferences
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1954-1958.
Abstract
In this paper, we will provide a fast polynomial-time algorithm for solving simple temporal problems (STPs) with piecewise linear convex preference functions and a utilitarian objective function. Our algorithm is motivated by the study of the linear programming (LP)-dual of a given mincost circulation problem (MCCP). We will also show how this duality relationship between simple temporal problems with preferences (STPPs) and MCCPs leads to fast incremental algorithms for solving the former. Our algorithms bear important implications in planning, scheduling and execution monitoring scenarios where (partial) plans are subject to repeated changes, and the most preferred solutions to the underlying STPPs have to be computed and updated fast (incrementally).
@inproceedings{ijcai2007p315,
title = {Fast (Incremental) Algorithms for Useful Classes of Simple Temporal Problems with Preferences},
author = {Kumar, T. K. Satish},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {1954--1958},
year = {2007},
url = {https://ijcai.org/proceedings/2007/315},
}
TY - CPAPER TI - Fast (Incremental) Algorithms for Useful Classes of Simple Temporal Problems with Preferences AU - Kumar, T. K. Satish T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 1954 EP - 1958 UR - https://ijcai.org/proceedings/2007/315 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
