Game theory applied to legged robotics: a variant of the dolichobrachistochrone problem

Paul Muench, PhD David Bednarz, PhD US Army RDECOM/TARDEC Warren, MI ABSTRACT We model the scenario between a robotic system and its operating environment as a strategic game between two players. The problem w ill be formulated as a game of timing. We will treat disturbances in a worst case scenario, i.e., as if they were placed by an opponent acting optimally. Game theory is a formal way to analyze the interactions among a group of rational players who behave strategically. We believe that behavior in the presence of disturbances using games of timing will reduce to optimal control when the disturbance is suppressed. In this paper we create a model of phase space similar to the dolichobrachistochrone problem. We discretize phase space to a simple grid where Player P is trying to reach a goal as fast as possible, i.e., with minimum cost. Player E is trying to maximize this cost. To do this, E has a limited number of "chips" to distribute on the grid. How should E distribute his resources and how should P navigate the grid? Rather than treating disturbances as a random occurrence, we seek to treat them as an optimal strategy INTRODUCTION Force does not exist for mobility, but mobility for force . Alfred Thayer Mahan Mobility is, by its nature, a means to an end; it does not exist for its own sake, but as a service to the larger force. Legged mobility stands as a nascent industry today due in part to the advances in control theory and computing power over the past few decades, but mainly it is due to the fact that the US government has poured such a vast amount of research into it. As this excitement inevitably winds down, it is the rather mundane problem of practical service to the military force that will ultimately determine the fate of the industry. The most likely first application for a legged robot is in dismounted logistics. The dismounted soldier is clearly overburdened; some type of off-loading robot that approaches the mobility of a dismounted soldier bearing a full march load would be of particular value to our military forces. Does this off-loading robot need to be a legged robot? The short answer is no. Unless we can show some quantifiable advantage in mobility, the additional cost of a legged platform is unjustifiable. Thus, the question becomes: How do we quantify mobility? Traditionally, we have defined mobility by looking at a list of things like: length of gap crossing, height of step obstacles, and terramechanics, i.e., soft soil mobility, to name a few. These discrete metrics do capture some of what we mean by mobility, but there is no standard way to quantify what each of these metrics is worth to us, i.e. to compare the relative value of one metric vs. the other. We have complicated the problem further now because we want add the capabilities of a legged robot to the list. Legged mobility is about narrow passageways and mountainous trails, where typically wide wheel based vehicles cannot traverse. Should we merely add these tall and narrow metrics to our rather ad-hoc definition of mobility in order to skew the decision matrix towards a legged platform? Rather than merely collecting a long list of metrics, we seek a general framework for mobility in the context of its value to the larger force. If we can show a quantifiable advantage to the force, we can begin to justify increased expenditures to achieve that