4. Features and Constraints

Introduction ¹

• As the number of elements in the state space increases the number of potential states that must be represented increases exponentially.
• Attempting to manage every state in a complex system individually is simply not practical as the number of states increases.
• Instead of attempting to manage states, we typically try to define a set of features that describes the state space.
• Constraints are limitations to action.
• Constraints are common when developing agents that operate in a larger environment.
• Constraint satisfaction is an important element of agent reasoning and is often factored into the problem search trees that are generated for agent-based problems.
• Finite CSP: a finite constraint satisfaction problem is one in which the number of potential solutions that must be searched to find a workable solution is finite and can be searched in a measurable period of time.
• Generate and Test Algorithms:
  • This approach is a brute force approach.
  • The idea is that every possible condition is generated in advance and then each solution is tested in order.
  • When a solution is found that fits the constraints it is returned and the search for a solution ends.
• Solving CSP through Search:
  • Construct a search space of potential solutions.
  • Use the search strategies (and optimization strategies) covered in previous units to make searching for a solution more efficient.
• Local Search:
  • In local search, the idea would be to assign some value to each of the variables perhaps just random numbers, and then ‘walk’ through incremental or neighboring values for each of these variable assignments until a fit is found that meets the criteria.  This process is repeated for each of the constraint variables.
  • Local search algorithms will typically have some form of a ‘stop’ variable or value that will limit the number of iterations that will be checked for a variable.   If a solution is not found within the limited-stop window then another random ‘try’ will be executed.
• Hill Climbing:
  • It is an example of a local search algorithm.
  • The idea is to start with a random solution and then to incrementally change the solution until a solution is found that meets the constraints.
  • It may get trapped in a local maximum or minimum; hence, the selection of neighbors uses randomization to avoid this.
• Stochastic Local Search: Hill climbing + randomization techniques for the first step, and every selection of a neighbor.
• Simulated annealing:
  • It is a stochastic local search algorithm; hence it uses randomization.
  • It uses a temperature variable to control the amount of randomness in the selection of neighbors.
  • The temperature slowly decreases over time, as we get closer to a solution, and also avoid getting trapped in a local maximum or minimum.
• Minimax Algorithm:
  • The minimax value of a node is the utility for MAX to be in the corresponding state, assuming both players play optimally from that state to the end of the game.

Reasoning with Constraints ²

• An algebraic variable, or variable, is used to name a feature. The domain of variable X, written d⁢o⁢m⁢(X), is the set of values the variable can take.
• A hard constraint, or simply constraint, specifies legal combinations of assignments of values to some of the variables.
• The set of variables involved in the constraint is the scope of the constraint.
• A constraint specifies a condition on these variables that is true or false for each assignment to the variables in the scope.
• Assignment A satisfies constraint c if A assigns the variables in the scope of c and the condition of c evaluates to true for A restricted to the scope of c. Assignment A violates constraint c if A assigns the variables in the scope of c and the condition of c evaluates to false for that assignment.
• A constraint satisfaction problem (CSP) consists of:
  • A set of variables.
  • A domain for each variable.
  • A set of constraints.
  • A solution is a total assignment that satisfies all of the constraints.

• The generate-and-test algorithm to find one solution is as follows: check each total assignment in turn; if an assignment is found that satisfies all of the constraints, return that assignment. A generate-and-test algorithm to find all solutions is the same except, instead of returning the first solution found, it enumerates the solutions.

• The consistency algorithms are best thought of as operating over a constraint network defined as:

  • There is a node (drawn as a circle or an oval) for each variable.
  • There is a node (drawn as a rectangle) for each constraint.
  • For every constraint c, and for every variable X in the scope of c, there is an arc ⟨X,c⟩. The constraint network is thus a bipartite graph, with the two parts consisting of the variable nodes and the constraint nodes; each arc goes from a variable node to a constraint node.
  • There is also a dictionary d⁢o⁢m with the variables as keys, where d⁢o⁢m⁢[X] is a set of possible values for variable X. d⁢o⁢m⁢[X] is initially the domain of X.
• Suppose constraint c has scope {X,Y1,…,Yk}. Arc ⟨X,c⟩ is arc consistent if, for each value x ∈ d⁢o⁢m⁢[X], there are values y1,…,yk where yi ∈ d⁢o⁢m⁢[Yi], such that the assignment {X=x,Y1=y1,…,Yk=yk} satisfies c. A network is arc consistent if all its arcs are arc consistent.

Minimax Algorithm ³

• It is widely used in two player turn-based games such as Tic-Tac-Toe, Backgammon, Mancala, Chess, etc.
• In Minimax the two players are called maximizer and minimizer.
• The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible.
• Time Complexity: O(b^d), where b is the branching factor and d is the maximum depth of the tree.
• Space Complexity: O(b*d).

Constraint satisfaction problems (CSPs) ⁴

• There is no optimal solution to a CSP, only a solution that satisfies all constraints.

NMCS4ALL: Optimization by Hillclimbing ⁵

References

‌ ‌

‌

---

1. Learning Guide Unit 4: Introduction | Home. (2025). Uopeople.edu. https://my.uopeople.edu/mod/book/view.php?id=454701&chapterid=555041 ↩

2. Poole, D. L., & Mackworth, A. K. (2017). Artificial Intelligence: Foundations of computational agents. Cambridge University Press. https://artint.info/2e/html/ArtInt2e.html Chapter 4 – Reasoning with Constraints ↩

3. Aradhya, A. L. (n.d.). Minimax algorithm in game theory | Set 1 (Introduction). GeeksforGeeks. https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/ ↩

4. (2025). Youtube.com. https://www.youtube.com/watch?v=lCrHYT_EhDs ↩

5. (2025). Youtube.com. https://www.youtube.com/watch?v=boTeFM-CVFw ↩