Abstract: In this talk we propose algorithms which determine the path that minimizes the expected value of a utility function over a dynamic probabilistic network with discrete or continuous real random variables (parameters) associated to each emerging arc. To obtain the optimal dynamic path from a source to sink node in the discrete case, we use a generalization of Bellman first-in-first-out labeling correcting algorithm used to determine the shortest path in directed networks with deterministic parameters associated to each arc. In the case where arc parameters are continuous random variables we propose algorithms involving multi-objective optimization. Additionally, some initialization techniques that improve the running times without jeopardizing memory are also considered. The topology of the networks is not known in advance, which means that we only have knowledge of the incoming (outgoing) arcs, and their parameters, of some specific node once we reach it. Thus the optimal path is determined in a dynamic way. Application: Whenever a strange object gets inside the bloodstream it is desirable to remove it as soon as possible in order to minimize live risk. The problem considered in this talk is the optimization of the expected value of a certain utility function, defined taking into account travel time between nodes, over a directed random network (bloodstream). To the network arcs there are associated random variables which represent the time that an object takes to travel from a node into another. Those variables are independent and have known discrete or continuous probability distributions. Starting from a source node (object entrance), one wants to determine the optimal (or the non-dominant optimal) path to a sink node that optimizes the expected value of the utility function. At the same time the problem solution (or non-dominated solutions) must answer the question "At a given time t where, approximately, is the object A in the network, knowing that its voyage started at node k?". Keywords: Optimal paths, random arc variables, object location inside a network
|