The shortest path problem on stochastic graphs is addressed. A stochastic optimal control problem is stated, for which dynamic programming can be used. The complexity of the problem leads us to look for a suboptimal solution making use of neural networks to approximate the cost-to-go function. By introducing the concept of "frontier", an alternative technique is given, for which any feasible policy leads to the destination node. Moreover by using a suitable algorithm, any approximation of the can be used to obtain a proper policy. Barren's results suggest the method might not incur the "curse of dimensionality".
Shortest path problems on stochastic graphs: a neuro dynamic programming approach / M. Baglietto; G. Battistelli; F. Vitali; R. Zoppoli. - STAMPA. - 6:(2003), pp. 6187-6193. (Intervento presentato al convegno 42nd IEEE Conference on Decision and Control tenutosi a Maui, USA) [10.1109/CDC.2003.1272268].
Shortest path problems on stochastic graphs: a neuro dynamic programming approach
BATTISTELLI, GIORGIO;
2003
Abstract
The shortest path problem on stochastic graphs is addressed. A stochastic optimal control problem is stated, for which dynamic programming can be used. The complexity of the problem leads us to look for a suboptimal solution making use of neural networks to approximate the cost-to-go function. By introducing the concept of "frontier", an alternative technique is given, for which any feasible policy leads to the destination node. Moreover by using a suitable algorithm, any approximation of the can be used to obtain a proper policy. Barren's results suggest the method might not incur the "curse of dimensionality".I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.