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