DocumentCode :
3278964
Title :
The value of sequential information in shortest path optimization
Author :
Rinehart, M. ; Dahleh, M.A.
fYear :
2010
fDate :
June 30 2010-July 2 2010
Firstpage :
4084
Lastpage :
4089
Abstract :
Consider an agent who seeks to traverse the shortest path in a graph having random edge weights. If the agent has no side information about the realizations of the edge weights, it should simply take the path of least average length, a deterministic optimization. We consider a generalization of this framework whereby the agent has access to a limited amount of side information about the edge weights as it traverses the graph. Specifically, we define a notion of side information and capacity, and we provide bounds on the agent´s performance relative to the total amount of side information it receives. The results are based in a graph reduction for shortest path optimization and an abstraction of sequential decision-making.
Keywords :
decision making; graph theory; optimisation; agent performance; deterministic optimization; graph reduction; least average length; random edge weight; sequential decision-making; sequential information; shortest path optimization; Algorithm design and analysis; Decision making; Gaussian distribution; Probability density function; Probability distribution; Random variables; Reactive power; Stochastic processes; Tail; Uncertainty;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
American Control Conference (ACC), 2010
Conference_Location :
Baltimore, MD
ISSN :
0743-1619
Print_ISBN :
978-1-4244-7426-4
Type :
conf
DOI :
10.1109/ACC.2010.5530628
Filename :
5530628
Link To Document :
بازگشت