程序代写案例-CS5011-Assignment 1
School of Computer Science, University of St Andrews, CS5011, 2020-21
CS5011: A1 - Search - Coastguard Rescue Simulations
Assignment: A1 - Assignment 1
Deadline: 17th of February 2021
Weighting: 25% of module mark
Please note that MMS is the definitive source for deadline and credit details. You are
expected to have read and understood all the information in this specification and any
accompanying documents at least a week before the deadline. You must contact the
lecturer regarding any queries well in advance of the deadline.
1 Objective
This practical aims to implement and evaluate a number of AI search algorithms applied to the
task of a coastguard rescue route planner.
2 Competencies
• Design, implement, and document AI search algorithms.
• Compare the performance of AI search algorithms.
• Test methods for optimising AI search.
3 Practical Requirements
3.1 Introduction
Operations of Search and Rescue1 provide help in emergency situation for people believed
to be in distress or in imminent danger. Search and Rescue operations bring significant com-
plexities and risks for rescue teams who must operate in adverse environments and under time
pressure to provide relief to those in danger. Autonomous robots have the potential to intervene
in these situations by searching areas for victims efficiently and timely to avoid further dangers
to human rescue teams. Testbeds and simulators have been developed in recent years for
robots and intelligent agents attempting to solve this problems. For example, the RoboCup
Rescue League2 is a well known robot competitions for rescue operations.
In this practical, we consider the problem of a coastguard rescue robot operating in the
Giant’s Causeway3. Our coastguard rescue robot is in charge of bringing a person in distress
to a location of safety. In order to do so, they have to plan an efficient route to ensure that the
person is looked after as soon as possible. The key characteristic of the Giant’s Causeway
environment is that the cliffs are formed by rocks shaped as hexagonal prims. We intend to
1https://en.wikipedia.org/wiki/Search_and_rescue
2https://www.robocup.org/domains/2
3https://en.wikipedia.org/wiki/Giant's_Causeway
1
develop an agent that simulates the behaviour of a coastguard rescue robot when planning
the route, and we refer to this simply as a robot or agent in the spec. The robot moves from a
hexagonal rock to the next but there are some obstacles in the path, due to the nature of the
environment where some hexagonal rocks are too tall to be reached, and some others can only
be reached and crossed from certain directions.
3.2 The task
Our robot is equipped with a 2D map of a portion of the coastal landscape where cells are all
hexagons of the same size as shown in Figure 1. The robot starts from a cell where we assume
a person is located P, and brings them back to a location of safety S in the most efficient way
to provide help as soon as possible. Which algorithm should the robot use?
1
P
S
1 1
c-column
r-row
0 1 2 3 4 5
0
1
2
3
4
5 1
1
2
1
2
Figure 1: Example map
The robot navigates the coastal map according to the following rules:
i. The environment is to be represented as a two-dimensional coordinate system (r, c) of
cells where r is the row and c is the column4. Maps for evaluation are provided with
the starter code (see Section 4.2) and are represented as Java 2D arrays of integers,
int[][] map=new int[rows][cols].
ii. Free cells are marked with a ‘0’ (white cells in Fig.1).
iii. The robot starts at cell P = (rp, cp) and then terminates at cell S = (rs, cs) (e.g., in Fig. 1
P=(1,1), S=(4,5)).
iv. The robot can only move along the grid, from free cell to free cell using the coordinate
system. We assume that each movement is from the centre of a cell to the centre of the
next cell and that each step has cost 1.
v. From a cell, the robot moves in the hexagonal map in all 6 directions labelled as the
respective cardinal points: South East (SE), East (E), North East (NE), North West (NW),
West (W), South West (SW), as shown in Figure 2.
4Please note this coordinate system is inverse with respect to a cartesian representation (x, y) where the row
number is a y coordinate, and the column number is an x coordinate. The (r, c) representation is in line with the
Java representation of 2D arrays
2
vi. There are two types of obstacles. Obstacles marked with ‘1’ represent rocks too tall to be
climbed, therefore the robot cannot move in any of those cells.
vii. Obstacles marked with ‘2’ represent rocks that can only be crossed on a line, from East
to West or from West to East as shown in Figure 3.
viii. The robot cannot go beyond any map boundaries.
ix. If a path cannot be found, the robot must inform the user with a failure message.
S5
1
4 3
6
2
NENW
W E
SESW
c-column
r-row
Figure 2: Navigation system
2
c-column
r-row
Figure 3: Obstacles of type 2
The aim of the practical is to implement and evaluate a set of AI search algorithms. There
are two main criteria for evaluating search algorithms: the quality of the solution (e.g., the path
cost of the robot route), and efficiency (e.g., the number of search states visited).
3.3 Basic Planning Agent
A basic coastguard planning robot makes use of uninformed search to identify a route to bring
the person to safety. Implement depth-first search (DFS), and breadth-first search (BFS) follow-
ing the general algorithm for search. Please ensure that your implementation makes minimal
changes between DFS and BFS. The algorithm should also avoid loops and redundant paths.
The tie-breaking strategy to be used for this part starts from SE and continues anti-clockwise
to SW. The priority is indicated with a number in the arrows in Figure 2 (1:SE, 2:E, 3:NE, 4:NW,
5:W, 6:SW).
For each algorithm, once the search has identified the route to the goal, it must be able to
construct the full path.
The output for this part must be the coordinates in the nodes of the frontier at each step
before polling a node, followed by three lines: the path represented as a sequence of (r, c)
coordinates within squared brackets separated by a single space, the path cost (double) and
the number of nodes visited (int). An example of the output for Figure 1 is formatted as follows:
[(1,1)]
[(1,2), (0,1), (0,0), (1,0), (2,1)]
.....
(1,1)(1,2)(1,3)(2,4)(3,5)(4,5)
5.0
22
If there is no path, the output should be:
3
[(1,1)]
[(1,2), (0,1), (0,0), (1,0), (2,1)]
....
fail
31
No other output should be printed.
3.4 Intermediate Planning Agent
An intermediate coastguard planning robot extends a basic one by making use of informed
search. For many search problems, better results can be obtained by using heuristics to choose
the state to explore next. Implement best-first search (BestF) and A*(AStar) search using the
heuristic discussed in the lectures for both algorithms. Your implementation should follow the
general algorithm for search. Tie-breaking strategies do not need to be applied in this part. The
output for this part must be formatted in the same way as the basic agent with one modification
to the frontier, where for each node we must print the coordinates and the f_cost separated by
a colon, for example:
[(1,1):4.0]
3.5 Advanced Agent
It is strongly recommended that you ensure you have completed the Requirements of the basic
and intermediate agent before attempting any of these requirements.
An advanced coastguard planning robot extends an intermediate one with at most two ad-
ditional functionalities. Please note that there is no benefit for implementing more than two.
Examples of additional functionalities include:
1. Find out about another search algorithm, such as bidirectional search, implement it and
evaluate it in comparison with the other developed approaches.
2. Develop a different heuristic for your informed search, implement it and evaluate the re-
sults, for example considering the actual geometrical distance travelled by the robot. A
tutorial of Hex grids is available from Redblobgames5 for ideas on other heuristics.
3. In addition to moving from a cell to the next, the robot might have to perform additional
actions, for example climbing a rock. Extend the approaches in the previous parts to
include the implementation of new types of actions and evaluate the algorithms under
those conditions. Remember to consider well how to account for these actions in the
heuristics for informed search.
4. Consider a team of 2 robots located in two adjacent cells which have to carry a stretcher
that covers two cells. The robots move simultaneously of one position at a time but cannot
be on the same coordinates at the same time, and must move such that they are located
in adjacent cells at all times otherwise the stretcher will fall. Adapt any of the previous
algorithms developed to perform this task. You can decide whether both robots move
every turn or one can stay still.
5. Assume that in the two robot problem above, there is another robot which helps guiding
the way. This third robot must also always be located in any cell adjacent to the other
two, but it can be at the back or front in a line, or on the side to help forming different
configurations (e.g. all in line, or grouped).
5https://www.redblobgames.com/grids/hexagons
4
6. Suggest your own advanced requirements: this must be of similar level of difficulty as
those suggested above. For a significant advancement, you may apply your search al-
gorithms to an extended search problem, or identify some other search algorithm and
propose its implementation and evaluation to solve the coastguard problem.
4 Code Specification
4.1 Code Submission
The program must be written in Java and your implementation must compile and run without
the use of an IDE. Your system should be compatible with the version of Java available on
the School Lab Machines (Amazon Corretto 11 – JDK11). Please do not use libraries that
implement search algorithms, but other libraries that are secondary to the objectives of the
practical can be used. Your source code should be placed in a directory called A1src/ and
should include all non-standard external libraries. The code must run and produce outputs as
described in the next sections.
Please note that code that does not adhere to these instructions may not be ac-
cepted.
4.2 Starter Code
For this practical, four starter classes are provided A1main.java, Conf.java, Map.java, and
Coord.java.
Map.java provides the coastal maps (MAP) to be used for evaluation, 5 in total, defined as
Enum Type6. This class also includes a few test maps that are used for discussion in class
(TMAP). TMAP00 is the map presented in Figure 1. Please do not modify the maps in this
class but you can add more if you wish.
Coord.java is a data structure for storing the coordinates, as row and column.
Conf.java provides the configurations (CONF) to be used for a specific run, 25 in total,
also defined as Enum Type. Each configuration includes a map corresponding to the above,
and the coordinates of the cells P, and S. Two test configurations are also included (TCONF).
For example, to run the configuration of Figure 1, we use TCONF00. Please do not modify the
configurations in this class but you can add more if you wish.
A1main.java contains only example code on how to retrieve a map to be used, how to
print it for debugging purposes, and some examples of the required output. This class can be
modified as required, however, please ensure that the final format of input and output is as that
produced in the sample code.
4.3 Running
Your code should run using the following command:
java A1main []
For example for BFS in Figure 1 we will use
java A1main BFS TCONF00
For the basic and intermediate agents, the output of the system must be as described as
we will perform some automatic tests on the required output.
5https://aws.amazon.com/corretto/
6https://docs.oracle.com/javase/tutorial/java/javaOO/enum.html
5
5 Report
You are required to submit a report describing your submission in PDF with the structure and
requirements presented in the additional document CS5011_A_Reports. The core sections
(Design, Implementation and Evaluation) have an advisory limit of 1500 words in total. The
report should include clear instructions on how to run your code. Consider the following points
in your report:
1. Describe the search problem components for the coastal guard planning problem.
2. Describe the implementation of the search strategy clearly, and the differences between
the various algorithms in your implementation.
3. Include details on how the successor function works.
4. When evaluating the algorithms, which algorithm is best in terms of the number of search
states visited? Which algorithm produces the best routes on the basis of path cost?
6 Deliverables
A single ZIP file must be submitted electronically via MMS by the deadline. Submissions in any
other format will be rejected.
Your ZIP file should contain:
1. A PDF report as discussed in Section 5
2. Your code as discussed in Section 4
7 Assessment Criteria
Marking will follow the guidelines given in the school student handbook. The following issues
will be considered:
• Achieved requirements
• Quality of the solution provided
• Examples and testing
• Insights and analysis demonstrated in the report
Some guideline descriptors for this assignment are given below:
• For a mark of 8 or higher: the submission implements part of the basic agent able to find
a path in at least one way, adequately documented or reported.
• For a mark of 11 or higher: the submission implements the basic agent fully. The code
submitted is of an acceptable standard, and the report describes clearly what was done,
with good style.
• For a mark of 14 or higher: the submission implements fully the basic agent with a good
attempt to the intermediate agent. It contains clear and well-structured code and a clear
report showing a good level of understanding of design and evaluation of search algo-
rithms.
6
• For a mark of 17: the submission implements fully the basic and intermediate agent. It
contains clear, well-designed code, together with a clear, insightful and well-written report,
showing in-depth understanding of design and evaluation of search algorithms.
• Above 17: the submission implements fully the basic and intermediate agent and one or
two advanced agent functionalities. The submission should demonstrate unusual clarity
of implementation, together with an excellent and well-written report showing evidence of
extensive understanding of design and evaluation of search algorithms.
8 Policies and Guidelines
Marking: See the standard mark descriptors in the School Student Handbook
https://info.cs.st-andrews.ac.uk/student-handbook/learning-teaching/feedback.html#
Mark_-Descriptors
Lateness Penalty: The standard penalty for late submission applies (Scheme B: 1 mark per
8 hour period, or part thereof):
https://info.cs.st-andrews.ac.uk/student-handbook/learning-teaching/assessment.html#
latenesspenalties
Good Academic Practice: The University policy on Good Academic Practice applies:
https://www.st-andrews.ac.uk/students/rules/academicpractice/
Alice Toniolo
[email protected]
January 25, 2021
7

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie