Scalable versions of differential game theory

Dr. Benjamin Mann, a program manager at DARPA, outlines 23 mathematical challenges for this century. Many of them are fairly well known problems that would appear in any such list. One challenge question that may not have been so easy to guess (although I fully support its selection) is “What new scalable mathematics is needed to replace the traditional PDE approach to differential games?“. There is also a passing mention of the importance of repeated games in Steve Smale’s list, under the heading of limits of intelligence – which I think is appropriate because whatever innovations come out of solving the generalized differential games challenge will also have a lot to do with the problem of creating an intelligent autonomous system.

Although they may sound quaint and obscure, differential games have a lot to do with many problems of current interest. One of the holy grails of robotics is an autonomous system that can reliably perform complex dynamical tasks in a hostile environment – a game against nature involving dynamics. At a conceptual level, we do understand many things about how to achieve this goal – the theory and practice of reinforcement learning (which, at the core, utilizes a stochastic and data-driven variant of the classical Hamilton-Jacobi-Bellman PDE) being a good example. However, the limitations of these general approaches have a lot to do with the limitations that Dr. Mann refers to – the computational complexity is unbearable in realistic settings. The best methods for the existing PDE based approaches to differential games involve innovative numerical techniques – multi-resolution grids, fast marching methods, etc. Still, these are all rather prohibitive for real time, high dimensional applications.

A direction that I find promising (as I have mentioned before) is that of using topological ideas to focus the algorithms, e.g., as in the SToMP project. There are some useful nuggets in recent publications by researchers who are part of this project. I am sufficiently intrigued that I am going to work on some aspects of this general problem myself. I hope to report back with more concrete and interesting results one of these days…


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s