scientific article; zbMATH DE number 3570374

From MaRDI portal
Publication:4140923





Consider an automated problem solver. If it has data enough at its disposal, it is able to derive a linear plan for solving a given problem, i.e., it offers a sequence of operators such that the execution of each operator assures the applicability of the next one, the first operator is applicable immediately and the last one realizes the desired goal. If the problem solver has not data enough, it is forced to take into consideration, at least in some cases, several possible continuations of an operator execution and to postpone the decision, which possibility will be actually follow, to the execution stage. In this way branching plans result, however, they are often too large to be applicable in practice. We propose a method how to reduce the extent of branching plans by omitting their ``less important parts. When a branching plan is actually applied, just one of its branches is followed, so we can ascribe to each node of this plan the probability that this node will be applied when the branching plan in question is used. Given an \(\varepsilon>0\), we can erase all the nodes for which this probability does not exceed \(\varepsilon\). The extent of the branching plan reduced in this way can be majorized by \(\varepsilon^{-1}\log_2(\varepsilon^{-1})\) when the conditional probabilities of all successors of each node under the condition that this node has been reached belong to the interval \((\varepsilon,1 - \varepsilon)\); this estimate depends only on \(\varepsilon\). In general, the extent of the reduced branching plan can be majorized by \(\varepsilon^{-1}\cdot\ell\), where \(\ell\) is the length (number of nodes) of the longest branch of the original branching plan. Some consequences of these estimates are also discussed. [For the entire collection see Zbl 0351.00017.]











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4140923)