Termination conditions / variable time length games

[rallen10]

I apologize if it is already covered in the documentation and I missed it, but I was wondering if there is a straightforward/existing approach for using termination conditions to end a game instead of a fixed-time endpoint or fixed-length horizon.

For example, take the basic target guarding problem (a pursuit-evasion, zero-sum game discussed in Isaacs' Differential Games book, pg 19, example 1.9.2). The game terminates when the distance between the pursuer and evader is less than a given threshold and the cost function is only evaluated at the moment of termination.

I could see how to use an "indicator function" to only evaluate the cost when the P-E distance is below the threshold (as described in section V.A of the ilqgames paper), but this doesn't terminate the game.

Thank you!

[dfridovi]

Hi @rallen10,

Very good question. I've wondered the same thing, though I'm afraid I'm not sure I see how it could be done cleanly. The first idea that comes to mind is to start with a set of strategies, then integrate forward a new trajectory as usual, then check and see when the game would terminate and compute the cost only at that time, then treat the game as finite time with that horizon and final cost, and somehow handle the fact that the final time will change at each iteration with some sort of heuristic. That sort of approach could totally totally work in this implementation, but I certainly haven't tried it and have no idea how well it would work. If you'd like to try something like that, I'd be happy to discuss further, and needless to say but if you do implement something for this problem based on this repository, I'd be happy to review a pull request and merge it in.

Best, David

[rallen10]

@dfridovi thank you for the insights. I'm still getting spun up with the library and I don't know how much time I'll be able to commit to it, but if I make any progress on this front, I'll discuss on this thread.

[rallen10]

@dfridovi I'm coming back to this work after a few months focusing on other projects. It looks like there has been a significant overhaul of some of the timing mechanics (e.g. https://github.com/HJReachability/ilqgames/commit/b3a45e9c3445026f855a60d242861fd9e9974504, https://github.com/HJReachability/ilqgames/commit/9b77c3873afa956d1a761392f2a6eb85ec5b2cb8).

It sounds simple, but I can't figure out how to even specify a fixed final time anymore; let alone a variable final time. Previously I used an expressions like

static constexpr Time kTimeHorizon = 30.0;
...
solver_.reset(new ILQSolver(dynamics, {p1_cost, p2_cost}, kTimeHorizon, params));

But that functionality seems deprecated. Now it seems that the time horizon is strictly hardcoded to be 10.0 in types.h (see here for reference )

Is there a simple way to change the time horizon of my problem to a different fixed values that I am missing?

[dfridovi]

Good catches. I realized that it was repetitive to force every new example to declare a separate time horizon, so I just moved timing constants into include/utils/types.h under the namespace ::ilqgames::time::. If you want to change it, just change that number. If you want a variable horizon, then you'll have to be very careful. To the best of my recollection, the only places time horizon shows up are in the core ILQ solver, the innermost loop LQ solver, and the operating point / strategy in each example. To make time horizon vary in each solve, you'll have to adjust each of these things very carefully... but you were always going to have to be very careful with these things and all the refactor has done is move a bunch of replicated member variables into a single float in a shared global namespace.