I think the problem with using food presents the same potential issues as simply hard limiting rests: you could end up with a bricked save if you rest too frequently and end up unable to progress. Since everything in this game is finite, and especially since you won't know how much food you'll find moving forward, AND since you likely won't find it all, it makes the number of rests you'll be able to take a mystery, which means it makes it even harder to plan. Or it's so abundant it means nothing and isn't really a limitation.
This is indeed the crux of the problem. A human DM can handle problems like this easily, but having an algorithm try and figure this out is quite difficult.
