In collaboration with Ministry of Science and Technology of Israel
Y Mirsky, A Cohen, R Stern, A Felner, L Rokack, Y Elovici, B Shapira
Eighth Annual Symposium on Combinatorial Search, 2015
Most work in heuristic search focused on path finding problemsin which the cost of a path in the state space is the sumof its edges’ weights. This paper addresses a different classof path finding problems in which the cost of a path is theproduct of its weights. We present reductions from differentclasses of multiplicative path finding problems to suitableclasses of additive path finding problems. As a case study,we consider the problem of finding least and most probablepaths in a Markov Chain, where path cost corresponds to theprobability of traversing it. The importance of this problemis demonstrated in an anomaly detection application for cyberspacesecurity. Three novel anomaly detection metrics forMarkov Chains are presented, where computing these metricsrequire finding least and most probable paths. The underlyingMarkov Chain is dynamically changing, and so fast methodsfor computing least and most probable paths are needed. Wepropose such methods based on the proposed reductions andusing heuristic search algorithms.