Constraint propagation with interval labels.

*(English)*Zbl 0642.68176Constraint propagation is often used in AI systems to perform inference about quantities. This paper studies one particular kind of constraint propagation, where quantities are labelled with signs or with intervals, and these labels are propagated through recorded constraints. We review the uses of such inference schemes in AI systems of various kinds, and evaluate their strengths and weaknesses. In particular, we determine the completeness and running time of constraint propagation for various kinds of labels and constraints.

##### MSC:

68T99 | Artificial intelligence |

Full Text:
DOI

##### References:

[1] | Waltz, D., Understanding line drawings of scenes with shadows, () |

[2] | Stefik, M., Planning with constraints (MOLGEN: part 1), Artificial intelligence, 16, 111-139, (1981) |

[3] | de Kleer, J.; Brown, J.S., A qualitative physics based on confluences, Artificial intelligence, 24, 7-83, (1984) |

[4] | Davis, R., Diagnosis via causal reasoning: paths of interaction and the locality principle, (), 88-92 |

[5] | Kuipers, B., Commonsense reasoning about causality: deriving behavior from structure, Artificial intelligence, 24, 169-203, (1984) |

[6] | Simmons, R., ‘commonsense’ arithmetic reasoning, () |

[7] | Brooks, R.A., Symbolic reasoning among 3-D models and 2-D images, Artificial intelligence, 17, 285-348, (1981) |

[8] | Ambler, A.P.; Popplestone, R.J., Inferring the positions of bodies from specified spatial relationships, Artificial intelligence, 6, 157-174, (1975) · Zbl 0303.68059 |

[9] | Lozano-Perez, T., The design of a mechanical assembly system, () |

[10] | Taylor, R.H., A synthesis of manipulator control programs from task-level specifications, () |

[11] | Sutherland, I.E., SKETCHPAD: A man-machine graphical communication system, () |

[12] | Borning, A., Thinglab—an object oriented system for building simulations using constraints, (), 497-499 |

[13] | Sussman, G.J.; Steele, G.L., CONSTRAINTS—A language for expressing almost hierarchical descriptions, Artificial intelligence, 14, 1-39, (1980) |

[14] | Southwell, R., () |

[15] | Hummel, R.A.; Zucker, S.W., On the foundations of relaxation labeling processes, IEEE trans. patt. anal. Mach. intell., 5, 267-287, (1983) · Zbl 0523.90086 |

[16] | McDermott, D.V.; Davis, E., Planning routes through uncertain territory, Artificial intelligence, 22, 107-156, (1984) |

[17] | Davis, E., Representing and acquiring geographic knowledge, () · Zbl 0825.68031 |

[18] | Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial intelligence, 25, 65-74, (1985) |

[19] | Mackworth, A.K., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061 |

[20] | Freuder, E., Synthesizing constraint expressions, Commun. ACM, 21, 11, 958-966, (1978) · Zbl 0386.68065 |

[21] | McDermott, D.V., Spatial inferences with ground, metric formulas on simple objects, () |

[22] | Boggess, L., Computational interpretation of English spatial prepositions, () |

[23] | Dean, T., Temporal imagery: an approach to reasoning about time for planning and problem solving, () |

[24] | Alefeld, G.; Herzberger, J., () |

[25] | Winograd, T., () |

[26] | Forbus, K., Qualitative process theory, Artificial intelligence, 24, 85-168, (1984) |

[27] | Sacerdoti, E., () |

[28] | Vere, S., Planning in time: windows and durations for activities and goals, IEEE trans. patt. anal. Mach. intell., 5, 3, 246-267, (1983) |

[29] | Fahlman, S.E., A planning system for robot contruction tasks, Artificial intelligence, 5, 1-49, (1974) |

[30] | Malik, J.; Binford, T.O., Reasoning in time and space, (), 343-345 |

[31] | Allen, J.F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 832-843, (1983) · Zbl 0519.68079 |

[32] | Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, () |

[33] | Williams, B.C., Qualitative analysis of MOS circuits, Artificial intelligence, 24, 281-346, (1984) |

[34] | Yemini, Y., Some theoretical aspects of position-location problems, (), 1-7 |

[35] | Kozen, D.; Yap, C.K., Algebraic cell decomposition in NC, (), 515-521 |

[36] | Richardson, D., Some undecidable problems involving elementary functions of a real variable, J. symbolic logic, 33, 514-520, (1968) · Zbl 0175.27404 |

[37] | Karmakar, N., A new polynomial time algorithm for linear programming, (), 302-311 |

[38] | Garey, M.R.; Johnson, D.S., () |

[39] | McAllester, D., An outlook on truth maintenance, () |

[40] | Luenberger, D.G., () |

[41] | Davis, E., Organizing spatial knowledge, () |

[42] | Kahn, K.; Gorry, G.A., Mechanizing temporal knowledge, Artificial intelligence, 9, 87-108, (1977) |

[43] | Dean, T., Planning and temporal reasoning under uncertainty, () |

[44] | Doyle, J., A truth-maintenance system, Artificial intelligence, 12, 231-272, (1979) |

[45] | McDermott, D.V., Data dependencies on inequalities, (), 266-269 |

[46] | Kuipers, B., Personal communication. |

[47] | Pratt, V.R.; Shostak, R., Deciding linear inequalities by computing loop residues, (), J. ACM, 28, 4, 769-779, (1981), Cited in · Zbl 0468.68073 |

[48] | Aho, A.V.; Hopcroft, J.; Ullman, J., () |

[49] | Fredman, M.L.; Tarjan, R., Fibonacci heaps and their uses in improved network optimization algorithms, (), 338-346 |

[50] | Allen, J.; Kautz, H., A model of naive temporal reasoning, (), 251-268 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.