CS 440: INTRODUCTION TO ARTIFICIAL INTELLIGENCE FALL 2021
Assignment 1
Fast Trajectory Replanning
Deadline: October 15, 11:55pm.
Perfect score: 100.
Assignment Instructions:
Teams: Assignments should be completed by teams of up to three students. You can work on this assignment individually
if you prefer. No additional credit will be given for students that complete an assignment individually. Make sure to write
the name and RUID of every member of your group on your submitted report.
Submission Rules: Submit your reports electronically as a PDF document through Canvas (canvas.rutgers.edu).
For programming questions, you need to also submit a compressed file via Canvas, which contains your code. Do not
submit Word documents, raw text, or hardcopies etc. Make sure to generate and submit a PDF instead. Each team of
students should submit only a single copy of their solutions and indicate all team members on their submission. Failure to
follow these rules will result in lower grade for this assignment.
Program Demonstrations: You will need to demonstrate your program to the TAs on a date after the deadline. The
schedule will be coordinated by the TAs. During the demonstration you have to use the file submitted on Canvas and
execute it on your personal computer. You will also be asked to describe the architecture of your implementation and
key algorithmic aspects of the project. You need to make sure that you are able to complete the demonstration and
answer the TAs’ questions within the allotted 10 minutes of time for each team. If your program is not directly running
on the computer you are using and you have to spend time to configure your computer, this counts against your allotted time.
Late Submissions: No late submission is allowed. 0 points for late assignments.
Extra Credit for LATEX: You will receive 10% extra credit points if you submit your answers as a typeset PDF (using
LATEX, in which case you should also submit electronically your source code). There will be a 5% bonus for electronically
prepared answers (e.g., on MS Word, etc.) that are not typeset. If you want to submit a handwritten report, scan it and
submit a PDF via Canvas. We will not accept hardcopies. If you choose to submit handwritten answers and we are not able
to read them, you will not be awarded any points for the part of the solution that is unreadable.
Precision: Try to be precise. Have in mind that you are trying to convince a very skeptical reader (and computer scientists
are the worst kind...) that your answers are correct.
Collusion, Plagiarism, etc.: Each team must prepare its solutions independently from other teams, i.e., without using
common notes, code or worksheets with other students or trying to solve problems in collaboration with other teams. You
must indicate any external sources you have used in the preparation of your solution. Do not plagiarize online sources and
in general make sure you do not violate any of the academic standards of the department or the university. Failure to follow
these rules may result in failure in the course.
Assignment Description
1 Setup
Consider the following problem: an agent in a gridworld has to move from its current cell to the given cell of a non-moving
target, where the gridworld is not fully known. They are discretizations of terrain into square cells that are either blocked
or unblocked.
Similar search challenges arise frequently in real-time computer games, such as Starcraft shown in Figure 1, and robotics.
To control characters in such games, the player can click on known or unknown terrain, and the game characters then move
autonomously to the location that the player clicked on. The characters observe the terrain within their limited field of
view and then remember it for future use but do not know the terrain initially (due to “fog of war”). The same situation
arises in robotics, where a mobile platform equipped with sensors builds a map of the world as it traverses an unknown
environment.
Figure 1: Fog of War in Starcraft
Assume that the initial cell of the agent is unblocked. The agent can move from its current cell in the four main compass
directions (east, south, west and north) to any adjacent cell, as long as that cell is unblocked and still part of the gridworld.
All moves take one time step for the agent and thus have cost one. The agent always knows which (unblocked) cell it is in
and which (unblocked) cell the target is in. The agent knows that blocked cells remain blocked and unblocked cells remain
unblocked but does not know initially which cells are blocked. However, it can always observe the blockage status of its
four adjacent cells, which corresponds to its field of view, and remember this information for future use. The objective of
the agent is to reach the target as effectively as possible.
A common-sense and tractable movement strategy for the agent is the following: The agent assumes that cells are unblocked
unless it has already observed them to be blocked and uses search with the “freespace assumption”. In other words, it moves
along a path that satisfies the following three properties:
1. It is a path from the current cell of the agent to the target.
2. It is a path that the agent does not know to be blocked and thus assumes to be unblocked, i.e., a presumed unblocked
path.
3. It is a shortest such path.
Whenever the agent observes additional blocked cells while it follows its current path, it remembers this information for
future use. If such cells block its current path, then its current path might no longer be a “shortest presumed-unblocked
path” from the current cell of the agent to the target. Then, the agent stops moving along its current path, searches for
another “shortest presumed-unblocked path” from its current cell to the target, taking into account the blocked cells that it
knows about, and then moves along this path. The cycle stops when the agent:
either reaches the target or
determines that it cannot reach the target because there is no presumed-unblocked path from its current cell to the
target and it is thus separated from the target by blocked cells.
In the former case, the agent reports that it reached the target. In the latter case, it reports that it cannot reach the target.
This movement strategy has two desirable properties:
1. The agent is guaranteed to reach the target if it is not separated from it by blocked cells.
2. The trajectory is provably short (but not necessarily optimal).
3. The trajectory is believable since the movement of the agent is directed toward the target and takes the blockage
status of all observed cells into account but not the blockage status of any unobserved cell.