this assignment will be to implement a working solver for the puzzle game Lunar Lockoutand Lunar Lockout is a puzzle game that is played on an NxN board.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Questions: Questions about the assignment should be asked on Piazza:

 A state of the Lunar Lockout puzzle. The red piece is a ’rover’ (or ’xanadu’), and the other pieces are ’helper robots’. The goal is to guide the ’rover’ pieces into the escape hatch at the center of the board.

https://piazza.com/utoronto.ca/summer2019/csc384/home.

If you have a question of a personal nature, please email the A1 TA, Randy, at rhickey@cs.toronto.edu or

a course instructor. Make sure to place [CSC384] and A1 in the subject line of your message.

1  Introduction

The goal of this assignment will be to implement a working solver for the puzzle game Lunar Lockout shown in Figure 1. Lunar Lockout is a puzzle game that is played on an NxN board. The game requires ’helper robots’ to guide ’rovers’ (also called ’xanadus’) into an escape hatch that is located at the center of the board. The rules hold that pieces (i.e. helper bots and rovers) must move one at a time in a straight line; they may not move diagonally. Pieces also cannot move through one another. Moreover, each piece may only move in the direction of a second piece, and it must move until it collides with the second piece and comes to a stop. Moves may sometimes take pieces directly across the escape hatch or result in a robot blocking the escape hatch (i.e. occupying the same square as the escape hatch). A rover cannot exit the escape hatch unless in lands directly atop it.

The game is over when all rovers have successfully made it through the escape hatch.

You can watch a video of Lunar Lockout game-play on YouTube, at https://www.youtube.com/watch?v=2BxPr55buhM. Our version of Lunar Lockout is slightly more complicated, however, as there may be more than one rover that needs to be guided to the escape hatch,

there can be an arbitrary number of helper robots, and the size of the board may be larger than 5x5.

2  Description of Lunar Lockout

Lunar Lockout has the following formal description. Read the description carefully.

The puzzle is played on a square board that is a grid board with N squares in the x-dimension and N

squares in the y-dimension. The dimension N is always odd.

Each state in the game contains the x and y coordinates for each robot as well as the x and y coordi- nates for each rover (or xanadu).

From each state, each robot and each rover can move North, South, East, or West, but only if there is a second robot or rover that lies in that direction. When a robot or rover moves, it must move all the way to the second piece until the pieces collide. For example, if a robot located at position (4, 0)

moves South toward a rover located at (4, 3), the robot will end at the location (4, 2). No two pieces

(robots or rovers) can move simultaneously or diagonally and pieces cannot pass through walls or

one another.

The escape hatch is always located in the center of the board (i.e. at the grid location ((N1)/2, (N 1)/2).

Once a rover arrives at the escape hatch, it exits the board through the escape hatch. It then disappears from subsequent play.

• Each movement is of equal

• The goal is achieved when all rovers have exited the board via the escape

Ideally, we will want our rovers to exit the escape hatch before they deplete our internal oxygen supplies. This means that with each problem instance, you will be given a computation time constraint. You must attempt to provide some legal solution to the problem (i.e. a plan) within this time constraint. Better plans will be plans that are shorter, i.e. that require fewer operations to complete.

Your goal is to implement an anytime algorithm for this problem: one that generates better solutions (i.e. shorter plans) the more computation time it is given.

 

3           Code You Have Been Provided

The file search.py, which is available from the website, provides a generic search engine framework and code to perform several different search routines. This code will serve as a base for your Lunar Lockout solver. A brief description of the functionality of search.py follows. The code itself is documented and worth reading.

An object of class StateSpace represents a node in the state space of a generic search problem. The base class defines a fixed interface that is used by the SearchEngine class to perform search in that state space.

For the Lunar Lockout problem, we will define a concrete sub-class that inherits from StateSpace. This concrete sub-class will inherit some of the “utility” methods that are implemented in the base class. Each StateSpace object s has the following key attributes:

• s.gval: the g value of that node, i.e., the cost of getting to that

• s.parent: the parent StateSpace object of s, i.e., the StateSpace object that has s as a suc- cessor. This will be None if s is the initial

• s.action: a string that contains that name of the action that was applied to s.parent to generate

1. s. Will be “START” if s is the initial state.

An object of class SearchEngine se runs the search procedure. A SearchEngine object is initialized with a search strategy (‘depth first’, ‘breadth first’, ‘best first’, ‘a star’, or ‘custom’) and a cycle checking level (‘none’, ‘path’, or ‘full’).

Note that SearchEngine depends on two auxiliary classes:

• An object of class sNode sn which represents a node in the search space. Each object sn contains a StateSpace object and additional details: hval, e., the heuristic function value of that state and gval, i.e. the cost to arrive at that node from the initial state. An f val f n and weight are tied to search nodes during the execution of a search, where applicable.

• An object of class Open is used to represent the search frontier. The search frontier will be organized in the way that is appropriate for a given search

When a SearchEngine’s search strategy is set to ‘custom’, you will have to specify the way that f values of nodes are calculated; these values will structure the order of the nodes that are expanded during your search.

Once a SearchEngine object has been instantiated, you can set up a specific search with:

init search(initial state, goal f n, heur f n, f val f n)

and execute that search with:

search(timebound, costbound)

The arguments are as follows:

• initial state will be an object of type StateSpace; it is your start

• goal f n(s) is a function which returns True if a given state s is a goal state and False other- wise.

• heuristic f n(s) is a function that returns a heuristic value for state s. This function will only be used if your search engine has been instantiated to be a heuristic search (e.g. best first).

• f val f n(sNode, weight) defines f values for states. This function will only be used by your search engine if it has been instantiated to execute a ‘custom’ search. Note that this function takes in an sNode and that an sNode contains not only a state but additional measures of the

state (e.g. a gval). The function also takes in a float weight. It will use the variables that are provided to arrive at an f value calculation for the state contained in the sNode.

• timebound is a bound on the amount of time your code will be allowed to execute the search. Once the run time exceeds the time bound, the search must stop; if no solution has been found, the search will return False.

• costbound is an optional parameter that is used to set boundaries on the cost of nodes that are explored. This costbound is defined as a list of three values. costbound[0] is used to prune states based on their g-values; any state with a g-value higher than costbound[0] will not be expanded. costbound[1] is used to prune states based on their h-values; any state with an h- value higher than costbound[1] will not be expanded. Finally, costbound[2] is used to prune states based on their f -values; any state with an f -value higher than costbound[2] will not be

For this assignment we have also provided lunarlockout.py, which specializes StateSpace for the Lunar Lockout problem. You will therefore not need to encode representations of Lunar Lockout states or the successor function for Lunar Lockout! These have been provided to you so that you can focus on implementing good search heuristics and an anytime algorithm.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of