|
Posted on January 28, 2016 @ 08:18:00 AM by Paul Meagher
In today's blog I want to begin exploring the concept of constraint satisfaction. Why? Because it is critical to understanding, both formally and informally, what creativity and design consist of.
An awareness of what your constraints are is important when it comes to designing anything. Design takes place within a set of constraints and the adequacy of a design is mainly determined by 1) whether you have your constraints right, and if so, 2) how good a fit your solution is to those constraints. Creativity is used to express these constraints and find a solution that is a good fit to these constraints.
A formal example of a constraint satisfaction problem is solving a set of linear equations. You may be familiar with solving linear equation problems from high school math.
Given:
x + y = 6
3x - y = 2
Solve for x and y.
One way to solve for x and y is by graphing each equation and finding out where they intersect. The point of intersection is the solution.
Using graphs is a good way to solve simple linear equation problems. If we add more equations with more terms then we need to use other techniques, such as Gaussian elimination or the Simplex algorithm, to solve this problem. There are powerful software tools, such as the GNU Linear Programming Kit (GLPK), that you can use to solve a variety of constraint satisfaction problems. I recommend you check out The GNU Linear Programming Kit, Part 1: Introduction to linear optimization (Part 2 and
Part 3) to see how linear constraints can be formally expresses and optimal solutions found using this software. GLPK is the type of software you might use to create your own version of Uber or Lyft.
The purpose of today's blog was to illustrate that a central idea in design and creativity, constraint satisfaction, can be expressed in mathematical terms in some cases. When we do so it can be quite powerful. There is another approach to solving constraint satisfaction problems that can be found in landscape design, software design, and permaculture design called design patterns. In my next blog I'll explore the use of design patterns as a more informal approach to expressing and solving constraint satisfaction problems.
Note: The graph above is from p. 126 of a 1990 textbook by Robert J. Schalkoff called Artificial Intelligence: An Engineering Approach. Robert devoted a useful chapter to Constraint Satisfaction Problems and the application of the logic programming language Prolog to such problems. It is interesting to note that IBM's Watson, the Artificial Intelligence (AI) that beat all the best Jeopardy! champions, is partially implemented in Prolog. Prolog offers another software toolkit for formally expressing and solving certain types of constraint satisfaction problems.
|
Animatronics and Humanoid Robots
