Applying the AI techniques to Computational Semantics

In this section, we will discuss how these techniques were modified and adapted for use in computational semantics.

  
Figure 5: Circuits of Inter-Dependence

We will demonstrate how constraint satisfaction information allowed us to identify ``circuits'' of inter-dependence in the input. Solutions for each circuit are synthesized apart from the rest of the problem. In addition, we used the natural tree-like form of our inputs to guide further synthesizing efforts. Figure 5 graphically displays how circuits of inter-dependence and tree-circuits can be combined into larger and larger circuits. At each level, solutions can be synthesized utilizing results from circuits below.

Branch-and-bound techniques were refined for use with the solution synthesis and constraint satisfaction methods. As each of the ``circuits'' mentioned above are synthesized, certain sub-circuits will no longer be dependent on nodes outside of the circuit. These sub-circuits can be optimized, with non-optimal solutions ``bound'' and eliminated. This particular merging of techniques accounts for the majority of savings produced by our system.

Finally, constraint satisfaction principles were capitalized on to change means-end text planning into a simpler and faster type of Constraint Satisfaction Problem (CSP), which can be solved using optimized CSP algorithms. A typical means-end planning session goes something like the following:

• main goal: communicate that Frank was lazily reading a book on the couch.
  • Plan1: assume ``read'' communicates basic Read-Event.
    • preconditions: none
    • effects: instantiate Read-Event
    • goal-minus-effects: still need agent, theme, location and attitude.
      • plan agent
      • plan theme
      • plan location
      • plan attitude
  • Plan2: assume ``peruse'' communicates Read-Event with ``lazy'' attitude
    • preconditions: none
    • effects: instantiate Read-Event with ``lazy'' attitude
    • goal-minus-effects: still need agent, theme, location
      • plan agent
      • plan theme
      • plan location
  • Plan3: assume ``potato'' communicates Read-Event with ``lazy'' attitude with location on the couch. Requires a co-eating event.
    • preconditions: Eating-Event
      • plan Eating-Event
    • effects: instantiate Read-Event with ``lazy'' attitude and location on the couch.
    • goal-minus-effects: still need agent, theme
      • plan agent
      • plan theme

Each of these plans would be constructed serially, with the most efficient plan being chosen at the end. In this case, Plan3 would be chosen if an Eating-Event could be planned to fulfill the precondition of ``potato'', otherwise Plan2 would be chosen.

Means-End planners typically are inefficient. Various methods have been used to improve their performance, with ``macro-planning'' receiving the most attention. Macro-planning will be discussed, and we will demonstrate how, by setting up our planner as a Constraint Satisfaction Problem, we can let the CSP techniques automatically identify macro-plans which can then be efficiently ``searched'' to find the optimal plan.