Neuro-Dynamic Programming for the Exploration of Unknown Graphs
| Authors: | Baglietto Marco, University of Genoa, Italy
Battistelli Giorgio, University of Genoa, Italy
Scardovi Luca, University of Genoa, Italy
Zoppoli Riccardo, University of Genoa, Italy |
|---|
| Topic: | 2.4 Optimal Control |
|---|
| Session: | Optimal Control Theory and Design Methods |
|---|
| Keywords: | Neural networks, Dynamic programming, Graph, Control, Entropy |
|---|
Abstract
In this paper, the problem of exploring stochastic graphs is addressed. The definition of the entropy related to the a-priori unknown parameters (the lengths of the a-priori unknown links) leads to the formulation of the problem as a stochastic optimal control one. The application of exact Dynamic Programming suffers the so-called curse of dimensionality. To overcome this drawback, an approximate technique is proposed making use of Neuro-Dynamic Programming. Exploiting the concept of frontier, any approximate solution of the problem is shown to generate a "proper" policy.
