Planning under Uncertainty in Constrained and Partially Observable Environments