Efficiency Analysis of Multiple-Context TMSs in Scene Representation

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Automated Reasoning

Multiple possible solutions can arise in many domains, such as scene interpretation and speech recognition. This paper examines the eficiency of multiple-context TMSs, such as the ATMS, in solving a scene representation problem which we call the Vision Constraint Recognition problem. The ATMS has been claimed to be quite eficient for solving problems with multiple possible solutions, even for problems with large databases. However, we present evidence that for large databases with multiple possible solutions (which we argue occur frequently in practice), such multiple-context TMSs can be very inefficient. We present a class of problems for which using a multiple-context TMS is both intrinsically interesting and ideal, but which will be computationally infeasible because of the exponential size of the database which the TMS must explore. To circumvent such infeasiblity, appropriate control must be exerted by the problem solver.