|
Posted on February 8, 2016 @ 08:29:00 AM by Paul Meagher
In a recent blog called Constraint Satisfaction: Part 1 I illustrated a couple of ways to represent constraints (i.e., line graphs, linear equations) and how to go about satisfying them (i.e., line intersection, gaussian elimination). In today's blog I want to provide a couple of other approaches to representing constraints to add more flexibility and precision to our thinking about constraints.
An example that illustrates a couple of different ways of representing constraints is from p.113 of Robert Schalkoff's book Artificial Intelligence (1990). In this example, Robert represents the goal of getting professorial tenure as involving the satisfaction of a number of constraints that can be represented in tree form as follows:
An equivalent way to represent these constraints is in the form of a PROLOG program which looks like this:
The main part of a PROLOG program consists of a set of facts and rules. These facts and rules constitute a small database which which can be queried. One question we might ask is "who will get tenure" which is formulated in this way in PROLOG:
?-gets_tenure(Who).
The answer PROLOG returns is "rjs" who is the book's author Robert J. Schalkoff.
So we can represent the constraints we face when trying to achieve some goal using tree graphs or we can use a logic programming language like PROLOG. The advantage of the latter is that we can draw inferences from our database of facts and rules, but this is probably not worth the effort in simple cases like this. We can run the logic program in our head.
I decided to exhibit a PROLOG program not because I expect people to start using it to solve logic problems, but because it provides a nice high-level language with which to express constraints. Also important is the idea that if you don't express these constraints (i.e., facts & rules) in the proper relationships, then you won't not be able to reach the conclusions/goals you want. You can't just write facts and rules down in an unstructured format. In this case, the graph provides the discipline we need to express our facts and rules with the proper relationships so that we can logically satisfy the get_tenure() goal.
The purpose of this blog is to illustrate that a couple more ways to represent constraints are with tree graphs and with structured logic programs consisting of facts and rules. It should be noted that the goal you are trying to achieve may have subgoals which have to be satisfied, hence the reason why tree graphs are useful. There may also be a strict or loose order to when these subgoals need to be achieved. In the graph above the subgoals on the top might have a higher priority (i.e., publishes()) than the subgoal at the bottom (i.e., teaches-well()). The order in which subgoals are achieved is often important in real world problem solving.
So if you are in the coffee shop thinking about your business and how you are going to achieve your goals, one way to achieve some precision in your thinking is to represent the constraints to achieving your goals with a tree graph or a simple logic program like the gets_tenure() example. There are other methods you can use like line graphs and sets of linear equations. The more precisely you can represent goals and constraints the better able you will be to reason about them.
On p. 114 of his textbook professor Schalkoff illustrated the sequence that PROLOG uses to figure out ?-gets_tenure(Who). This may not represent the order in which a professor satisfies tenure subgoals but it does illustrate useful further details: 1) there are often a significant number of subgoals that have to be achieved in order to achieve a significant high level goal, 2) your abstract tree structure needs to eventually "bottom out" with an actual binding to some real object or result. Constraint satisfaction involves satisfying our low level goals in concrete form so they propagate back towards achieving our high level goals.
|
