Graph planning with expected finite horizon
Chatterjee, Krishnendu
Doyen, Laurent
Graph planning gives rise to fundamental algorithmic questions such as shortest path, traveling salesman problem, etc. A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.
IEEE
2019
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/7402
Chatterjee K, Doyen L. Graph planning with expected finite horizon. In: <i>34th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2019:1-13. doi:<a href="https://doi.org/10.1109/lics.2019.8785706">10.1109/lics.2019.8785706</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1109/lics.2019.8785706
info:eu-repo/semantics/altIdentifier/isbn/9781728136080
info:eu-repo/semantics/altIdentifier/arxiv/1802.03642
info:eu-repo/semantics/openAccess