CS 440编程代写、代写c++、Python程序

日期：2021-10-03 11:07

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.