Project #2: Structured Problem Solving and Planning

ROB311: Artificial Intelligence
Project #2: Structured Problem Solving and Planning

Overview
In this project, you will gain further experience with three different topics we have discussed in lecture: formal
logic, constraint satisfaction problems, and vehicle motion planning. The goals are to:
• implement an algorithm for logical inference over definite clauses;
• use local search to solve the classic N-queens constraint satisfaction problem (for N > 100); and
• build a randomized motion planning solver for a Dubins-type vehicle.
The project has three parts, worth a total of 50 points. All submissions will be via Autolab; you may submit
as many times as you wish until the deadline. To complete the project, you will need to review some material
that goes beyond that discussed in the lectures—more details are provided below. The due date for project
submission is Saturday, February 26, 2022, by 23:55 EST.
As in Project #1, each part already has a starter script with some basic setup code and a simple problem
instances ready to go. Once again, do not modify function names, file names, or import statements! Please
also remember to test your functions one at a time so that an incomplete function does not cause Autolab to
hang and timeout.
Part 1: Inference with Definite Clauses
Propositional logic can be used to answer questions about entailment, i.e., whether one fact follows logically
from another set of facts. If we restrict ourselves to definite clauses, which are Horn clauses with exactly one
positive literal, very efficient inference algorithms exist, such as forward-chaining (see AIMA pg. 258). Your
task is to:
1. Implement a simple inference engine to solve problems in propositional logic involving definite clauses
only. The engine should accept a knowledge base KB and a query q (which is a propositional symbol)
and return true if KB entails q (and false otherwise).
You will submit your implementation of inference_method.py through Autolab. Please see the docstring
of pl_fc_entails in inference_method.py for a description of the inputs and outputs. The definite
clauses will be provided to you in the form of DefiniteClause objects from support.py.
Part 2: The N-Queens Problem
The N-queens problem is a classic search and constraint satisfaction problem—the goal is to place N queens
on an N × N chessboard such that no queen ‘attacks’ any other. A queen attacks any piece in the same row or
column, or that lies along the same diagonal on the board. An example (partial) partial attempt at a solution
1 of 4
ROB311: Artificial Intelligence Project #2: Structured Problem Solving and Planning
to the 8-queens problem is shown in Figure 1. We will refer to a queen attacking another queen as a ‘conflict’.
72 Chapter 3. Solving Problems by Searching
Figure 3.5 Almost a solution to the 8-queens problem. (Solution is left as an exercise.)
Although efficient special-purpose algorithms exist for this problem and for the whole
n-queens family, it remains a useful test problem for search algorithms. There are two main
kinds of formulation. An incremental formulation involves operators that augment the state INCREMENTAL
FORMULATION
description, starting with an empty state; for the 8-queens problem, this means that each
action adds a queen to the state. A complete-state formulation starts with all 8 queens on COMPLETE-STATE
FORMULATION
the board and moves them around. In either case, the path cost is of no interest because only
the final state counts. The first incremental formulation one might try is the following:
• States: Any arrangement of 0 to 8 queens on the board is a state.
• Initial state: No queens on the board.
• Actions: Add a queen to any empty square.
• Transition model: Returns the board with a queen added to the specified square.
• Goal test: 8 queens are on the board, none attacked.
In this formulation, we have 64 · 63 ··· 57 ≈ 1.8 × 1014 possible sequences to investigate. A
better formulation would prohibit placing a queen in any square that is already attacked:
• States: All possible arrangements of n queens (0 ≤ n ≤ 8), one per column in the
leftmost n columns, with no queen attacking another.
• Actions: Add a queen to any square in the leftmost empty column such that it is not
attacked by any other queen.
This formulation reduces the 8-queens state space from 1.8 × 1014 to just 2,057, and solutions
are easy to find. On the other hand, for 100 queens the reduction is from roughly 10400 states
to about 1052 states (Exercise 3.5)—a big improvement, but not enough to make the problem
tractable. Section 4.1 describes the complete-state formulation, and Chapter 6 gives a simple
algorithm that solves even the million-queens problem with ease.
Figure 1: Example partial solution (with a conflict on the main diagonal) to the 8-queens problem (AIMA pg.
72).
Luckily, N-queens is quite easy for local search algorithms to solve, because solutions are distributed fairly
densely throughout the state space (see AIMA pg. 221). Your tasks are to:
1. Implement a greedy initialization algorithm for the N-queens problem, that is, an algorithm which starts
with one queen on the board (randomly choose the row for the first column) and adds new queens incrementally until all queens have been placed. The greedy strategy should attempt to minimize the number
of conflicts for each new queen that is added. Use the function template in the handout code called
initialize_greedy_n_queens.py. The function should return a 1 × N vector, where the zeroindexed i
th entry is the row number of the queen in the i
th column. The row numbers should also be in the
set {0, 1, . . . , N − 1} (i.e., zero-indexed). The docstring of initialize_greedy_n_queens provides
examples and further details.
2. Build a solver that makes use of the Min-Conflicts heuristic (AIMA pg. 221) to place all queens on an
N × N board without any conflicts. Note that this will be a randomized algorithm, and hence different runs may produce different results—in certain instances, you may need to run your function two
(or more) times to produce a valid solution. Use the function template in the handout code called
min_conflicts_n_queens.py, which has extra details in its function’s docstring. You will be graded
by a procedure that calls your implementation of initialize_greedy_n_queens to produce an initialization, then uses your min_conflicts_n_queens implementation to search for a conflict-free solution
(see the example in the handout code).
As with Project #1, you will submit your implementations of initialize_greedy_n_queens.py and
min_conflicts_n_queens.py through Autolab. For both the initialization and heuristic search functions,
be sure to break any ties (in terms of the minimum conflicts heuristic) randomly - this is key for getting the
algorithm to perform well.
2 of 4
ROB311: Artificial Intelligence Project #2: Structured Problem Solving and Planning
Part 3: Motion Planning for a Dubins Vehicle
The rapidly-exploring random trees (RRT) algorithms is a widely-used algorithm for sample-based robot path
planning, in part because it is able to take into account kinodynamic constraints. These are constraints on
velocity and acceleration, for example. RRTs are also able to handle nonholonomic constrains, that is, constraints that involve the possible paths taken (parallel parking is such an example: a car cannot move sideways
instantaneously). The algorithm has been discussed in lecture and a demonstration can be seen in this video.
A popular class of kinodynamic paths is known as Dubins paths. A Dubins path is the shortest curve that
connects two points in the two-dimensional Euclidean plane with a constraint on the curvature of the path,
and with prescribed initial and final tangents (vectors) to the path. An assumption is made that the vehicle
on the path can only travel forward. This is a very useful model for many robotics applications. You can read
more about Dubins path here. An example of such a path is shown in Figure 2. Your task is to:
1. Implement an RRT-based planner for a Dubins-type vehicle in a 2D planar world with circular obstacles.
The RRT planning function should accept an RRT problem object (of class RRT_dubins_problem) which
contains: a map (2D world), a list of circular obstacles, a starting pose, a goal pose and plenty of helper
functions for Dubins path generation. The function should produce a list of nodes along a valid path
starting from the start node and reaching the goal state. Use the function template in the handout code
called rrt_planning.py. Precise instructions and conditions have been provided in the comments
of this file. The RRT_dubins_problem class and a simple test have been implemented in the helper
file rrt_dubins_problem.py. Helpful Dubins-type path generation functions have been provided in
dubins_path_planning.py. Keep in mind that there are time limits on the tests, which implies it is
essential to reach the goal pose quickly.
HINT: A purely random exploration strategy is not fast enough in finding the goal. If you already know
the goal pose, a “smarter” random exploration strategy can be employed for a faster solution.
Figure 2: Example Dubins LRL path.
Note that a major chuck of the problem setup and function implementation has already been provided; for example rrt_dubins_problem.py already contains a propagation and a collision checking function, but you
are encouraged to read these implementations to understand the big picture for a successful implementation.
The provided code is well documented for your clarification and understanding.
3 of 4
ROB311: Artificial Intelligence Project #2: Structured Problem Solving and Planning
You will submit and check your implementations of the planning function in rrt_planning.py file through
Autolab.
Submission and Grading
We would like to reiterate that only functions implemented for the Autolab will affect your marks. There are
other questions in the sections above, but only those that ask you to submit a function via Autolab will affect
your total. The remainder are useful for your understanding or are there to aid you in creating the functions
for Autolab. Points for each portion of the project will be assigned as follows:
• Inference with Definite Clauses – 15 points (5 tests × 3 points per test)
Each test will check whether your function is able to correctly determine if q is inferred by KB.
Time limit: 5 seconds per test.
• N-Queens – 15 points (3 tests × 5 points per test)
Each test will provide a positive integer N and check whether your code outputs an assignment of N
queens to the N × N chessboard such that no queens are attacking one another.
Time limit: 5 seconds for N ≈ 100, 10 seconds for N ≈ 500, 20 seconds for N ≈ 1000.
• Motion Planning for a Dubins Vehicle – 20 points (2 tests with 15 and 5 points respectively.)
Each test will give you an obstacle map, a start pose and a goal pose. Your function must return a
kinematically feasible set of nodes from the start pose that reach the final goal pose with no collisions.
The tests will check whether nodes on your paths are correct (we fix the seed for the pseudo-random
number generator to ensure results will be the same between runs).
Time limit: 20 seconds for Test 1, 40 seconds for Test 2.
Please note the time limits are are included to catch bugs and infinite loops in submitted algorithm implementations. Correct solutions will run in far less time than the time limits.
Total: 50 points
To submit your code, put it in a .tar file with this command (from a directory containing all the requisite
.py files:
tar cvf handin.tar *.py
Grading criteria include: correctness and succinctness of the implementation of support functions, proper
overall program operation, and code commenting. Please note that we will test your code and it must run successfully. Code that is not properly commented or that looks like ‘spaghetti’ may result in an overall deduction
of up to 10%.
4 of 4