We consider both discrete and continuous control problems constrained by a fixed budget of some resource, which may be renewed upon entering a preferred subset of the state space. In the discrete case, we consider both deterministic and stochastic shortest path problems on graphs with a full budget reset in all preferred nodes. In the continuous case, we derive augmented PDEs of optimal control, which are then solved numerically on the extended state space with a full/instantaneous budget reset on the preferred subset. We introduce an iterative algorithm for solving these problems efficiently. The method's performance is demonstrated on a range of computational examples, including optimal path planning with constraints on prolonged visibility by a static enemy observer.

In addition, we also develop an algorithm that works on the original state space to solve a related but simpler problem: finding the subsets of the domain ``reachable-within-the-budget''.

This manuscript is an extended version of the paper published in SIAM J. on Control and Optimization. In the journal version, Section 3 and the Appendix were omitted due to space limitations.

• An expanded pre-print on arXiv.
• A (shorter) journal version.

We release the implementation code of our algorithms under GNU GPL license. You can download it from here. Please refer to the ReadMe.txt in the source code distribution for instructions on compiling the code and setting up the numerical tests.

• The first author was supported in part by ONR grants N0014-03-1-0071, N00014-07-1-0810, N00014-08-1-1119,
  DOE grant DE-FG02-05ER25710, an ARO MURI through Rice University and the CHASE MURI grant 556016.
• The second, third, and fourth authors' work was supported by the National Science Foundation
  through the Research Experiences for Undergraduates Program at Cornell University.
• The last author was supported in part by the National Science Foundation (DMS-1016150).