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, fo
r 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作业君
