Understanding network emulation software, Mininet Total: 9 points The purpose of this assignment is to give you hands-on experience in developing a custom virtual network using the mininet network emulation software. The mininet network supports software Openflow switches, Open vSwitch (a.k.a., OVS), and an OpenFlow SDN controller, POX, that will help us realize a virtual Software Defined Network. The SDN paradigm separates the control plane (e.g., routing algorithms) from the data plane (e.g., forwarding). The control plane runs as a logical centralized program on commodity servers (instead of switches). Setting up your machine: 1. Install virtual box (if not already installed) ○ Download and install the appropriate executable for Windows ○ Download the appropriate executable for Ubuntu and follow the instructions: 2. Download the VM from the following link. This VM has mininet, OVS, and POX installation. Warming up: We must build certain fundamentals before starting to configure OVS and run the SDN controller over the mininet network emulation platform. Go through the videos mentioned for each topic. 1. Mininet utilizes process network namespaces in Linux which allows you to do lightweight emulation (like virtualization). Watch the following video (watch only until 13:55 mins): Introduction to Linux Network Namespaces 2. Watch this video for an introduction to mininet and its usage. You can run the commands in parallel on your VM for understanding. Introduction to Mininet 3. Watch this video for an introduction to Open vSwitch and its usage. You will understand packets such as packet In, packet Out, and flow mod communicated between the OVS and the controller. Introduction to Open vSwitch 4. This video facilitates understanding of running an SDN application over a mininet+OVS+POX environment, Customizing SDN control The slides for this video are available here (slide number 35 – 53) Miscellaneous links: 1. If you want to start mininet installation from scratch on your machine (not recommended for this assignment). Download/Get Started With Mininet a. If you want the VM with GUI do the following. $sudo apt-get install xinit x11-xserver-utils lxde $startx lxde 2. Mininet commands and usage with OVS and POX. Mininet Walkthrough Mininet Home Page Q.1. Setting up the topology for the assignment: A. Follow the Mininet tutorial to create a custom network topology shown in the figure below. (2 points) i. Take hints from the example custom Mininet topology which is available at ~/mininet/custom/topo-2sw-2host.py ii. You can run Mininet with this custom topology as follows. $sudo mn –custom ~/mininet/custom/topo-2sw-2host.py –topo mytopo –mac –switch ovsk –controller remote B. Verify the topology by checking the network configuration (within the mininet prompt) as follows. (1 point) mininet> netQ.2. Refer to the tutorials 5 and 7 to answer this question. a. Create a bottleneck at the interface of host h1 using “tc”. (1 point) b. Generate TCP traffic between the hosts h1 and h6 using iperf. (1 point) c. Use Wireshark/tcpdump at host h1 to capture the packets generated in (b) (1 point) d. Plot the congestion window using the packet dump obtained from (c) (3 points) What to submit: Submit the following documents in one folder. 1. A short write-up with snapshots/plots followed by an explanation of your observations 2. Include the python code for the custom topology, scripts for Q.2, and the plot
Note: This is a lengthy assignment. If you do not start by tomorrow you will not be able to finish it on time. Warm-up 1. Watch this video to have a conceptual understanding of I/O multiplexing techniques such as select, poll, and epoll calls in Linux. This was also done in Tutorial 4. 2. Understand traditional, synchronous TCP socket programming from Tutorial 2. 4. Understand how to set up your system for TCP client/server experiments. 5. Please go through the FAQ before starting the assignment. The objective of this assignment is to analyze the performance of synchronous and asynchronous TCP servers. Write the TCP server socket programs in C language only. TCP client: We have provided the concurrent TCP client program here, and its usage is explained in the README file. The assignment comprises the following tasks. 1. Write the following TCP server programs: a. Concurrent server program with multiple processes (using fork system call) [3] b. Concurrent server program with multiple threads (using pthreads) [3] c. Non-blocking server programs that implement I/O multiplexing using i. select() system call [5] ii. poll() system call [5] iii. epoll API [5] All non-blocking designs must support 4000 concurrent connections (i.e., listener file descriptors). 2. Server function: The server program (all designs in (1)), after accepting the incoming request, does the following. [points included in (1)] a. Read the payload and cast it to a 64-bit unsigned integer, n. b. Write a function, fact(n), to compute the factorial of the “n”; if n>20, then calculate the factorial of 20. c. Send the factorial result as the response message back to the client. 3. For each server program in (1), perform separate experiments with number of concurrent client connections equal to 500, 1000, and 3000. Each connection generates 50 requests. For each combination of , do the following. a. Data collection: You must capture all the packets communicated between the client and the server on the server’s interface using a tool such as tcpdump or wireshark. [2] b. Write python scripts that take the pcap file generated in (a), and computing the following metrics for each server experiment. Show your observations in a plot. i. Average throughput for each TCP flow (in bits per second) [2.5] ii. Average latency for each TCP flow (in milliseconds) [2.5] c. Observe the following metrics. Show your observations in a table and analyze/justify it. i. Server process’s CPU utilization (use “top” or “htop” command) [2.5] ii. Server process’s memory utilization (use “time -v” command) [2.5] Note: Do not use any print statements (while sending/processing requests) when you are observing the metrics. Such I/O operations will slow down the process. ———————
The overall objective of this assignment is to help you build and understand the working of a TCP receiver. The assignment is decomposed into three primary components: 1. Building the ByteStream class. 2. Building a reassembler to assemble back the segments received from the sender in the correct order. 3. Building the actual TCP receiver by stitching together the ByteStream and Reassembler. Getting Starter code 1. Download and extract the zip file from google classroom. 2. cd into the project directory and create a new directory called build. 3. Now cd into the build directory and run cmake .. to configure the project. 4. Once the project is configured, run make in the same directory to build the project. 5. Once the project is built without any errors, you can run ctest to run all the tests for the TCP receiver. 6. As you can see, all the tests will fail. Once you have implemented all the classes correctly, all the tests must pass. Background on TCP Generally when we want to retrieve a webpage or want to send an email to someone, the applications rely on a mechanism called Reliable Byte Stream to communicate between each other. Byte Stream is an essential abstraction for applications to send data or communicate with each other. A Reliable Byte Stream ensures that the bytes received at the receiver side are exactly the same and in the same order as sent by the sender. In reality however, the Internet doesn’t provide a service of reliable byte-streams. Instead, the only thing the Internet really does is to give its “best effort” to deliver short pieces of data, called Internet datagrams, to their destination. Each datagram contains some metadata (headers) that specifies things like the source and destination addresses—what computer system it came from, and what computer system it’s headed towards—as well as some payload data (up to about 1,500 bytes) to be delivered to the destination computer. The two systems have to cooperate with each other to make sure that the bytes in the stream eventually gets delivered, in the correct order to the correct destination on the other side. They also have to tell each other how much data they are prepared to accept from the other system and make sure not to send more than the other side is wdilling to accept. All this is done using an agreed-upon scheme set down in 1981 called the Transmission Control Protocol or TCP. Part I: Building ByteStream [10 points] A ByteStream class, as the name itself suggests, is basically a container that stores a collection of bytes from which bytes can be read or written to. In the first part of the assignment, your goal will be to build a ByteStream class that will be used to represent a reliable byte stream. These are some of the properties of byte stream : 1. Bytes are written on the input side and read out from the output side (use a data structure that allows pushing the byte from one side and popping from the other side). 2. The byte stream is finite. The writer can end the input and no more bytes can be written. 3. When the reader has read to the end of the stream, it will reach EOF (End of File), that is no more available bytes to read 4. Your abstraction will also be initialized with a particular capacity which limits the total amount of bytes that can be held in memory at once (which are not read yet). 5. The writer would not be allowed to write into the byte stream if it exceeds the storage capacity. 6. As the reader reads bytes from the stream, the writer is allowed to write more. 7. This ByteStream will be used in a single threaded context and therefore you don’t have to worry about readers, writers, locking or race conditions. The interface for the ByteStream is available inside src/byte_stream.hh. ● You need to implement the methods of this interface inside src/byte_stream.cc. To test your implementation, run make inside the build directory to build the project and ctest -R ‘^byte_stream’, to run all the tests associated with byte_stream. Part II: Building a reassembler [10 points] In the second part of the assignment, you will be building a special data structure called Reassembler, which will be responsible for reassembling the string of bytes obtained from the sender and storing it in the ByteStream. The TCP sender is dividing its byte stream up into short segments (substrings not more than 1460 bytes apiece) so that they can fit inside a datagram. But as we discussed before, the only thing the Internet does is to give its “best efforts” to deliver the datagram to the receiver. In reality, the network might reorder these datagrams, drop them or deliver them more than once. It is the job of the receiver to reassemble the segments into a contiguous stream of bytes that the sender originally intended. This is where reassembler comes into play. The Reassembler receives substrings from the sender which consists of a string of bytes along with an index of the first byte of the string that represents its position within the larger stream. As a simple example, let’s say the sender wants to send “abcdefgh” to the receiver and assume that the sender has divided the entire payload into two substrings “abcd” and “efgh”. Now the indexes for these substream will be the following : [0] : abcd [4] : efgh Now on the receiver end lets say the the datagrams are received in following order (efgh,4) -> (abcd,0) The Reassembler using these unique indexes will paste the substrings into the byte stream in the correct order (abcdefgh). The full (public) interface of the reassembler is described by the Reassembler class in the src/reassembler.hh header. What should the Reassembler store internally ? The insert method informs the Reassembler about a new excerpt of the ByteStream, and where it fits in the overall stream (the index of the beginning of the substring). In principle, the Reassembler needs to handle three categories of knowledge : 1. Bytes that are the next bytes in the stream. The Reassembler should push these to the Writer as soon as they are known. 2. Bytes that fit within the stream’s available capacity but can’t yet be written, because earlier bytes remain unknown. These should be stored internally in the Reassembler (buffered basically). 3. Bytes that lie beyond the stream’s available capacity. These should be discarded. The Reassembler will not store any bytes that can’t be pushed to the ByteStream either immediately, or as soon as earlier bytes become known. The goal of this behavior is to limit the amount of memory used by the Reassembler and ByteStream, no matter how the incoming substrings arrive. We’ve illustrated this in the picture below. The “capacity” is an upper bound on both: 1. The number of bytes buffered in the reassembled ByteStream (shown in green), and 2. The number of bytes that can be used by “unassembled” substrings (shown in red)Blue: Bytes popped already Green: Bytes Buffered in stream (in the correct order) Red: Bytes buffered internally by the Reassembler (for the indexes that cant be sent to the byte stream because the previous indexes have not arrived) Grey: Unacceptable indexes (More than the capacity of the buffer) Part III: Building the actual TCP receiver by stitching together the ByteStream and Reassembler [20 points] In the third part of the assignment, you will implement an actual TCP receiver that accepts a TCPSegment from the sender and utilizes the Reassembler from the previous part of the assignment to correctly write the bytes into the byte stream. One thing to note is that apart from accepting the bytes, the TCPReciever also needs to generate messages back to the sender. These “receiver messages” are responsible for telling the sender: 1. Index of “first unassembled” byte called acknowledgement number or ackno. 2. The available capacity in the output ByteStream. This is called the “window size”. Together the ackno and window size describe the receiver’s window: a range of indexes that the TCP sender is allowed to send. Using the window, the receiver can control the flow of incoming data, making the sender limit how much it sends until the receiver is ready for more. The main task associated with this part of the assignment is to wire up the Reassembler and the ByteStream class and implement the TCP Receiver interface inside tcp_reciever.hh. The hardest part will involve thinking about how the TCP will represent each byte’s place in the stream a.k.a sequence number. Note : Placing a breakpoint inside the methods of this interface and debugging the relevant test cases can help you figure out the solution if you are stuck somewhere Translating between 64-bit indexes and 32-bit seqnos In the earlier part of the assignment, you built a Reassembler that reassembles substring where each substring has a 64bit stream index with the first byte in the stream always zero. In the TCP headers however, in order to conserve space, the indexes of substring are represented using a 32 bit sequence number. This adds three complexities : 1. Your implementation needs to plan for 32-bit integers to wrap around Streams in TCP can be arbitrarily long and 2^32 bytes is only 4GB which is not so big. So once the sequence number counts up to 2^32-1, the next byte will have the sequence number 0. 2. TCP sequence numbers start at a random value In order to improve robustness and avoid getting confused by old segments belonging to earlier connections between the same endpoints, TCP makes sure that sequence numbers can’t be guessed and therefore don’t start at 0. Instead the first sequence number in the stream is a random 32 bit integer called the ISN (Iniital Sequence Number). This is the number that represents the zero point or SYN (beginning of stream). Rest of the sequence numbers are simply ISN+x (mod 2^32) where x is the index of byte (1st byte, 2nd byte etc). 3. The logical beginning and end, each occupy one sequence number These sequence numbers (seqnos) are transmitted in the header of each TCP segment. It’s also sometimes helpful to talk about the concept of an “absolute sequence number” (which always starts at zero and doesn’t wrap), and about a “stream index” (what you’ve already been using with your Reassembler: an index for each byte in the stream, starting at zero). To understand the distinction between sequence number, absolute sequence number and stream index refer to the example below. Consider the byte stream contains “cat”. If the SYN happened to have seqno 2^32 − 2, then the seqnos, absolute seqnos, and stream indices of each byte are: element SYN C A T FIN seq_no 2^32-2 2^32-1 0 1 2 abs_seq_no 0 1 2 3 4 stream_index 0 1 2 Sequence Number : – Start at ISN – Include SYN/FIN – 32 bits wrapping – “Seq_no” Absolute Sequence Number – Start at 0 – Include SYN/FIN – No wrapping 64bits – “abs_seq_no” Stream Indices – Start at 0 – Omit SYN/FIN – 64bit No wrap – “Stream_index” To perform conversion between absolute sequence number and sequence number, a new type name WrappingInt32 contains a method called wrap and unwrap for performing the conversion. You need to implement both wrap and unwrap methods inside wrapping_integers.hh and wrapping_integers.cc You can test your implementation of wrapping integers by running ctest -R ‘^wrapping_integers’ inside the build directory. Finally the objectives of Part 3 of the assignment are : 1. Implement the conversion routines of WrappingInt32 2. Implement tcp_reciever.hh interface To test the entire implementation of TCP receiver, run ctest inside the build folder.
CSE 112 Computer Organization Introduction and Instructions ● This will be a group assignment, each student in the group will be marked separately. Therefore try to make sure that work is roughly divided equally among all the members of the group. ● In this assignment, you will have to design and implement a custom assembler and a custom simulator for a given ISA. ● You are not restricted to any programming language. However, your program must read from stdin and write to stdout. ● You must use GitHub to collaborate. You must track your progress via git. ● The automated testing infrastructure assumes that you have a working Linux-based shell. For those who are using Windows, you can either use a VM or WSL. QUESTION DESCRIPTION: There are a total of four questions in this assignment: 1. Designing and Implementing the assembler. 2. Designing and Implementing the simulator. 3. Extending the functionality of the assembler-simulator set-up to handle simple floating-point computations. 4. A bonus question based on the assembler and simulator. The bonus will be worth 10%. TEST CASES: We will release some test cases with the assignment so that you can test your implementations. During the evaluations, a superset of these test cases would be provided to you, on which you will get graded. DEADLINES: You will have two deadlines for this assignment: 1. The mid-evaluation: b. You will be tested mostly on the test cases already provided to you with the assignment. c. However, we might add some other test cases as well. d. You will only be evaluated on the assembler. (20%) 2. The final evaluation: b. You should also have completed Q3(10%). c. You will be evaluated on a much larger set of test cases this time. d. You will also be evaluated on the bonus question at this stage. ❖ The mid evaluation will be worth 20% of your final assignment grade. The final evaluation will be worth the rest 80% of your final assignment grade. The bonus will be worth 10% making the total 110%. GRADING: a. Q1 and Q2 are mandatory questions. b. In Q1, you will have to make an assembler. c. In Q2, you have to make a simulator for which detailed information is mentioned in the respective questions. d. Q3 is an extension of the functionality of the assembler-simulator set-up that you build. e. Q4 is a bonus question. ● For Q1 and Q2: Grading will be based on the number of test cases that your program passes. a. Assembler: The test cases are divided into 3 sets: i. ErrorGen: These tests are supposed to generate errors ii. simpleBin: These are simple test cases that are supposed to generate a binary. iii. hardGen: These are hard test cases that are supposed to generate a binary. b. Simulator: The test cases are divided into 2 sets: ● For Q3: a. Assembler: The test cases are divided into 2 sets: ■ ErrorGen: These tests are supposed to generate errors ■ SimpleBin: These are simple test cases which are supposed to generate a binary. b. Simulator: The test cases are divided into single set: ■ simpleBin: These are simple test cases which are supposed to generate a trace. For Q4: ● You need to design 5 instructions on your own. ● Upgrade your Assembler to handle those instructions. ● Upgrade your simulators to simulate the newly defined instructions. ● You need to create a readme file for the instructions that you have created. EVALUATION PROCEDURE: 2) On the day of your demo, a compressed archive of all tests will be shared with you on google classroom. This archive will include other test cases as well, which will not be provided to you beforehand. 3) On the day of evaluation, you must b) Prove the integrity of the tests archive by computing the sha256sum of the archive. To compute the checksum, you can run “sha256sum 4) Then you can extract the archive and replace the “automatedTesting/tests” directory. 5) Then you need to execute the automated testing infrastructure, which will run all the tests and finally print your score. 1. Any copying of code from your peers or from the internet will invoke the institute’s Assignment Description ISA description: Consider a 16 bit ISA with the following instructions and opcodes, along with the syntax of an assembly language which supports this ISA. The ISA has 6 encoding types of instructions. The description of the types is given later. Opcode Instruction Semantics Syntax Type 00000 Addition Performs reg1 = reg2 + reg3. If the computation overflows, then the overflow flag is set and 0 is written in reg1 add reg1 reg2 reg3 A 00001 Subtraction Performs reg1 = reg2- reg3. In case reg3 > reg2, 0 is written to reg1 and overflow flag is set. sub reg1 reg2 reg3 A 00010 Move Immediate Performs reg1 = $Imm where Imm is a 7 bit value. mov reg1 $Imm B 00011 Move Register Move content of reg2 into reg1. mov reg1 reg2 C 00100 Load Loads data from mem_addr into reg1. ld reg1 mem_addr D 00101 Store Stores data from reg1 to mem_addr. st reg1 mem_addr D 00110 Multiply Performs reg1 = reg2 x reg3. If the computation overflows, then the overflow flag is set and 0 is written in reg1 mul reg1 reg2 reg3 A00111 Divide Performs reg3/reg4. Stores the quotient in R0 and the remainder in R1. If reg4 is 0 then overflow flag is set and content of R0 and R1 are set to 0 div reg3 reg4 C 01000 Right Shift Right shifts reg1 by $Imm, where $Imm is a 7 bit value. rs reg1 $Imm B 01001 Left Shift Left shifts reg1 by $Imm, where $Imm is a 7 bit value. ls reg1 $Imm B 01010 Exclusive OR Performs bitwise XOR of reg2 and reg3. Stores the result in reg1. xor reg1 reg2 reg3 A 01011 Or Performs bitwise OR of reg2 and reg3. Stores the result in reg1. or reg1 reg2 reg3 A 01100 And Performs bitwise AND of reg2 and reg3. Stores the result in reg1. and reg1 reg2 reg3 A 01101 Invert Performs bitwise NOT of reg2. Stores the result in reg1. not reg1 reg2 C 01110 Compare Compares reg1 and reg2 and sets up the FLAGS register. cmp reg1 reg2 C 01111 Uncondition al Jump Jumps to mem_addr, where mem_addr is a memory address. jmp mem_addr E 11100 Jump If Less Than Jump to mem_addr if the less than flag is set (less than flag = 1), where mem_addr is a memory address. jlt mem_addr E 11101 Jump If Greater Than Jump to mem_addr if the greater than flag is set (greater than flag = 1), where mem_addr is a memory address. jgt mem_addr E 11111 Jump If Equal Jump to mem_addr if the equal flag is set (equal flag = 1), where mem_addr is a memory address. je mem_addr E 11010 Halt Stops the machine from executing until reset hlt F where reg(x) denotes register, mem_addr is a memory address (must be an 7-bit binary number), and Imm denotes a constant value (must be an 7-bit binary number). The ISA has 7 general purpose registers and 1 flag register. The ISA supports an address size of 7 bits, which is double byte addressable. Therefore, each address fetches two bytes of data. This results in a total address space of 256 bytes. This ISA only supports whole number arithmetic. If the subtraction results in a negative number; for example “3 – 4”, the reg value will be set to 0 and overflow bit will be set. All the representations of the number are hence unsigned. The registers in assembly are named as R0, R1, R2, … , R6 and FLAGS. Each register is 16 bits. Note: “mov reg $Imm”: This instruction copies the Imm(7bit) value in the register’s lower 7 bits. The upper 9 bits are zeroed out. Example: Suppose R0 has 1110_1010_1000_1110 stored, and mov R0 $13 is executed. The final value of R0 will be 0000_0000_0000_1101. FLAGS semantics The semantics of the flags register are: ● Overflow (V): This flag is set by {add, sub,mul, div} when the result of the operation overflows. This shows the overflow status for the last executed instruction. ● Less than (L): This flag is set by the “cmp reg1 reg2” instruction if reg1 < reg2 ● Greater than (G): This flag is set by the “cmp reg1 reg2” instruction if the value of reg1 > reg2 ● Equal (E): This flag is set by the “cmp reg1 reg2” instruction if reg1 = reg2 The default state of the FLAGS register is all zeros. If an instruction does not set the FLAGS register after the execution, the FLAGS register is reset to zeros. The structure of the FLAGS register is as follows: Unused 12 bits V L G E 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 The only operation allowed in the FLAGS register is “mov reg1 FLAGS”, where reg1 can be any of the registers from R0 to R6. This instruction reads FLAGS register and writes the data into reg1. All other operations on the FLAGS register are prohibited. The cmp instruction can implicitly write to the FLAGS register. Similarly, conditional jump instructions can implicitly read the FLAGS register. Example: R0 has 5, R1 has 10 Implicit write: cmp R0 R1 will set the L (less than) flag in the FLAGS register. Implicit read: jlt 0001001 will read the FLAGS register and figure out that the L flag was set, and then jump to address 0001001. Binary Encoding The ISA has 6 types of instructions with distinct encoding styles. However, each instruction is of 16 bits, regardless of the type. ● Type A: 3 register type Opcode (5 bits) Unused (2 bits) reg1 (3 bits ) reg2 (3 bits) reg3 (3 bits ) 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ● Type B: register and immediate type opcode (5 bits) Unused (1 bit) reg1 (3 bits) Immediate Value (7 bits) 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ● Type C: 2 registers type Opcode (5 bits) Unuse (5 bits) d reg1 (3 bits) reg2 (3 bits ) 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ● Type D: register and memory address type opcode (5 bits) Unused (1 bit) reg1 (3 bits) Memory Address (7 bits) 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ● Type E: memory address type opcode (5 bits) unused (4 bits) Memory Address (7 bits) 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ● Type F: halt opcode (5 bits) unused (11 bits) 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Binary representation for the register are given as follows:- Register Address R0 000 R1 001 R2 010 R3 011 R4 100 R5 101 R6 110 FLAGS 111 Executable binary syntax The machine exposed by the ISA starts executing the code provided to it in the following format, until it reaches hlt instruction. There can only be one hlt instruction in the whole program, and it must be the last instruction. The execution starts from the 0th address. The ISA follows von-neumann architecture with a unified code and data memory. The variables must be allocated in the binary in the program order. code (last instruction) halt variables Questions: Q1: Assembler: ● Empty line: Ignore these lines ● A label ● An instruction ● A variable definition Each of these entities have the following grammar: ● The syntax of all the supported instructions is given above. The fields of an instruction are whitespace separated. The instruction itself might also have whitespace before it. An instruction can be one of the following: ○ The opcode must be one of the supported mnemonic. ○ A register can be one of R0, R1, … R6, and FLAGS. ○ A mem_addr in jump instructions must be a label. ○ A Imm must be a whole number = 0. ○ A mem_addr in load and store must be a variable. ● A variable definition is of the following format: var xyz which declares a 16 bit variable called xyz. This variable name can be used in place of mem_addr fields in load and store instructions. All variables must be defined at the very beginning of the assembly program. The assembler should be capable of: 1) Handling all supported instructions 2) Handling labels 3) Handling variables 4) Making sure that any illegal instruction (any instruction (or instruction usage) which is not supported) results in a syntax error. In particular you must handle: a) Typos in instruction name or register name b) Use of undefined variables c) Use of undefined labels d) Illegal use of FLAGS register e) Illegal Immediate values (more than 7 bits) f) Misuse of labels as variables or vice-versa g) Variables not declared at the beginning h) Missing hlt instruction i) hlt not being used as the last instruction You need to generate distinct readable errors for all these conditions. If you find any other illegal usage, you are required to generate a “General Syntax Error”. The assembler must print out all these errors. 5) If the code is error free, then the corresponding binary is generated. The binary file is a text file in which each line is a 16bit binary number written using 0s and 1s in ASCII. The assembler can write less than or equal to 128 lines. Input/Output format: ● The assembler must read the assembly program as an input text file (stdin). ● The assembler must generate the binary (if there are no errors) as an output text file (stdout). Example of an assembly program: var X mov R1 $10 mov R2 $100 mul R3 R2 R1 st R3 X hlt The above program will be converted into the following machine code 0001000100001010 0001001001100100 0011000011010001 0010101100000101 1101000000000000 Q2: Simulator: You need to write a simulator for the given ISA. The input to the simulator is a binary file (the format is the same as the format of the binary file generated by the assembler in Q1. The simulator should load the binary in the system memory at the beginning, and then start executing the code at address 0. The code is executed until hlt is reached. After execution of each instruction, the simulator should output one line containing an 7 bit number denoting the program counter. This should be followed by 8 space separated 16 bit binary numbers denoting the values of the registers (R0, R1, … R6 and FLAGS). …. The output must be written to stdout. Similarly, the input must be read from stdin. After the program is halted, print the memory dump of the whole memory. This should be 128 lines, each having a 16 bit value. ….. Your simulator must have the following distinct components: 1. Memory (MEM): MEM takes in an 7 bit address and returns a 16 bit value as the data. The MEM stores 256 bytes, initialized to 0s. 2. Program Counter (PC): The PC is an 7 bit register which points to the current instruction. 3. Register File (RF): The RF takes in the register name (R0, R1, … R6 or FLAGS) and returns the value stored at that register. 4. Execution Engine (EE): The EE takes the address of the instruction from the PC, uses it to get the stored instruction from MEM, and executes the instruction by updating the RF and PC. The simulator should follow roughly the following pseudocode: initialize(MEM); // Load memory from stdin PC = 0; // Start from the first instruction halted = false; while(not halted) { Instruction = MEM.fetchData(PC); // Get current instruction halted, new_PC = EE.execute(Instruction); // Update RF compute new_PC PC.dump(); // Print PC RF.dump(); // Print RF state PC.update(new_PC); // Update PC } MEM.dump() // Print the complete memory Q3: Floating-Point Arithmetic: CSE112_Floating_point_representation: NO sign bit, 3 exponent bits, and 5 mantissa bits. ● In the registers, only the last 8 bits will be used in computations and initialization for the floating-point numbers. Modify the assembler and simulator to include arithmetic operations for floating-point numbers of the form(precision) given above. Specifically, include the following functions: 10000 F_Addition Performs reg1 = reg2 + reg3. If the computation overflows, then the overflow flag is set and reg1 is set to 0 addf reg1 reg2 reg3 A 10001 F_Subtraction Performs reg1 = reg2 – reg3. In subf reg1 reg2 reg3 A case reg3 >reg2, 0 is written to reg1 and overflow flag is set. 10010 Move F_Immediate Performs reg1 = $Imm where Imm is an 8-bit floating-point value. movf reg1 $Imm B Note: ● For moving 1.5 into reg1. The instruction(in assembly language) should be: movf reg1 $1.5 ● Keep in mind that in floating point multiplication $Imm is 8 bit so you need to make a new Type B syntax with 8 bit. ● The students must only apply the operations for the floating-point numbers that can be represented in the given system(8 bits), else they should report it as an error. Q4: (Bonus) Designing New Instructions In Q4. You need to design five instructions on your own or take help of online resources. After their design you need to upgrade your assembler to include those instructions.Similarly you need to upgrade your simulator to simulate those instructions. Upgrade Assembler 5% Upgrade Simulator 5% A proper readme file with description of the instructions (opcode, semantics etc) should be included and proper explanation should be given to respectiveTA during evaluation. N.B. You are not allowed to change the existing opcode.
Objective: The objective of this assignment is to explore the process of generating an instruction-based dataset for model training in Natural Language Processing (NLP). Additionally, students will fine-tune a pre-trained model using the newly created instruction-based dataset and compare its performance with the original instructions. Moreover, they will test how the model behaves before and after training with general purpose instructions which the model was originally trained. To save on time, I decided to use the pretrained model that we made in assignment 2. After copying and renaming the model to LlamaBase I finetuned it further with the new imdb dataset. after which it was finetuned again with the original data from assignment 2. The 2 rounds of finetuning were done in trainLlama2B.py and trainLlama2C.py From there, I ran my evaluation code, Evaluation.py and Evaluation3B.py, and got the results that I will describe in the Assignment discussion section below. Instructions Environment Setup To run, first load the environment from the environment.yml file with: conda env create -f environment.yml Then activate it: conda activate unsloth_env I used the same environment as the previous assignment. Fine Tuning To run the fine-tuning run: python trainLlama2B.py or python trainLlama2C.py Execution In order to run inferences for the models run: python Evaluation.py then python Evaluation3B.py Assignment Discussion 3a.) Evaluate the saved model from 2.b and 2.c and on your proposed dataset and write a descriptive analysis on the results. Create a table like the sample table provided. Normal Evaluation CodeBleuRouge-L Rouge-L Average BERTScore BERTScore Average Llama2Base 0.3166 Recall: 0.5060 Precision: 0.1531 0.2938 Recall: 0.8675 Precision: 0.7910 0.8286 F1 Score:0.2222 F1 Score:0.8273 Llama2 b. 0.1945 Recall: 0.4785 Precision: 0.1209 0.2621 Recall: 0.8467 Precision: 0.7870 0.8164 F1 Score:0.1868 F1 Score:0.8154 Recall: 0.5029 Recall: 0.8643 Llama2 c. 0.3285 Normal Evaluation0.2992 0.8310 Precision: 0.1619 Precision: 0.7988 F1 Score:0.2328 F1 Score:0.8300 Using my dataset seems to have negatively affected the model. Especially for code. Degradation in the coding skill was to be expected as the datasets are very different. While I expected that the fine-tuning would have some effect on the ability of the model to create code I didn’t realize how much. Out of the 20 prompts used for generation little code was produced. Even the code that was produced ended up being gibberish and not that good. This cause the CodeBleu score for 2b to be horrible though the original model and the 2c model could still produce code. Surprisingly though it did well on the Rouge and Bert scores. 3b.) Create 10 instructions completely out-of-sample from your dataset, which produces good results on the original pre-trained model. Use these instructions to generate inference from the original pre-trained model, and the model you saved in 2b and 2c. Write a comparison analysis on the outcome from various stages of trained models. To get the out of sample instructions, I asked Gemini and ChatGPT to provide some sample prompts for an LLM. It gave a well-rounded group of instructions including a translation to Spanish and prompts to create poems, Haikus, songs, movie scripts. and jokes. In my base mode, the prompt to “Translate this sentence into Spanish: ‘The quick brown fox jumps over the lazy dog.” generated a particularly good inference. The model gave: Translate this sentence into Spanish: ‘The quick brown fox jumps over the lazy dog.’ Translating the sentence into Spanish… ‘El rapaz veloz y listo salta sobre el perro dormilón’ Translated sentence: ‘The quick brown fox jumps over the lazy dog.’ Initiating the process, let’s achieve perfection! The translation of the sentence in Spanish is: ‘El rapaz veloz y listo salta sobre el perro dormilón.’ The translation is: ‘The quick brown fox jumps over the lazy dog.’ The words ‘rapaz’ and ‘perro’ are masculine, while ‘veloz’ and ‘dormilón’ are adjectives that describe the nouns ‘rapaz’ and ‘perro’ respectively. The adjective ‘veloz’ is an antonym of ‘dormilón’ which means ‘lazy’. The adjective ‘veloz’ means ‘quick’ and the adjective ‘rapaz’ means ‘brown’. The noun ‘rapaz’ means ‘fox’ and the noun ‘perro’ means ‘dog’. This is actually wrong. See ‘rapaz’ actually means ‘raptor’ So in actuality the code translated it to: ‘The quick and clever raptor jumps on the sleeping dog.’ Which is a shame for the dog. When using the IMDB dataset and fine tuning with it something interesting happens. the result this time was: ./Llama2b output: Translate this sentence into Spanish: ‘The quick brown fox jumps over the lazy dog.’ Answer: ‘La fiera rápida negra saltó sobre el perro manso.’ Answer: ‘La fiera rápida negra saltó sobre el perro manso.’ Comment: Welcome to Spanish.SE! Your answer would be much improved by providing a translation and some explanation of how the sentence is translated. Now this is still wrong. The answer it gave actually translates too ‘The fast black beast jumped on the tame dog.’ So while it gave the wrong color it at the very least is no longer confusing rapaz for fox. After finetuning with the combined dataset, the 3c model ended up translating it to this: Instruction 9 Translate this sentence into Spanish: ‘The quick brown fox jumps over the lazy dog.’./Llama2c output: Translate this sentence into Spanish: ‘The quick brown fox jumps over the lazy dog.’ Translating the sentence… ‘El rapaz listo y veloz salta sobre el perro perezoso.’ Translated the sentence. Translating… python *import pyttsx3 *engine = pyttsx3.init() *engine.say(‘El rapaz listo y veloz salta sobre el perro perezoso.’) *engine.runAndWait() ** This translates to The clever and fast raptor jumps over the lazy dog. It is still wrong but hey at least the dog survived! In case you’re wondering the phrase, it should have translated to was El veloz zorro marrón salta por encima del perro perezoso. or El rápida zorro marrón salta por encima del perro perezoso. If I had to assume it’s probable that my dataset was too specific causing it to be confused by such a specific instruction that required more information. The original dataset was: 1) A lot bigger(36K rows vs a little more than 400 rows) 2) Much more varied. It is interesting to see how much fine-tuning can affect LLMs. Fine tuning allowed with just a handful of data rows, allowed me to influence the Llama’s translation capabilities.
Q1: Given a set of data points shown in figure 1, sketch (a schematic trend of change is enough, no need to calculate the exact numbers) a plot of how the average square distance of a data sample with respect to its corresponding cluster center will change as the number of clusters k increases.Fig 1Q2: Consider applying SLIC superpixelling to the image in Fig 2 (a). A sample result for 300 superpixels is shown in Fig 2 (b). Note how the resulting superpixels in uniform regions (e.g. those outlined in yellow) tend to be hexagonal. Why does this occur?(a) (b) Fig 2Q3: For Mean-Shift clustering, what happens to the number of clusters as the window size or bandwidth is increased? Explain your answer.Coding:• Apply skimage.segmentation.slic to 100075-Bear.png and show outputs through skimage.segmentation.mark_boudaries. Fix sigma to 5 for all experiments. o Compare the results for 50, 100, 200, and 300 segments and discuss. o Fix the segment number to 100. Compare and discuss the results when compactness is set to 1, 10, and 100. o Fix segment number to 100 and compactness to 10. Compare and discuss the results when the maximum number of iterations is set to 1, 2, 3, 4 and 5. • Apply sklearn.cluster.KMeans to the data in Q1. Change the initialization method to see its impact on final average square distance of all samples with respect to the clustering centers. Past Quiz Questions: • AY2122 quiz 2: Q1 (clustering)
Theoretical:Q1: Consider images of size 12×12 with pixel values ranging from 0 to 15. For the following image histograms, estimate the mapped intensity values after histogram equalization.Figure 1Original Intensity Intensity after histogram equalization (a) (b) (c) (d) (e) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Q2: Consider the source image shown in (a) and the filter kernel shown in (b). What is the resulting value at positions (0,0), (2,2) and (4,3) if you were to apply cross-correlation, convolution, and 3×3 median filtering, with the use of zero-padding on the borders? Positions are denoted as (row,column) in the unpadded image.Pixel position Output pixel intensity cross- correlation convolution median filtering (0,0) (2,2) (4,3)(a) source image (b) kernel Figure 2 Coding (see CS4243-Tutorial-01.ipynb): • Install basic python packages: imutils, opencv-python, scikit-image • Load and display House.jpg • Visualize the (R,G,B) channels; visualize the normalized colour and intensity images • Convert RGB image into HSV colour space and visualize the (H,S,V) channels • Resize an image such that the dimensions are 2X, 0.5X and 0.05X the original size• For Capture.jpeg o Visualize the image histogram o Access a pixel value: what is the pixel intensity of (100,800) o Access a window of data: crop out the stadium • Write your own algorithm for histogram stretching and equalization. Visualize the resulting histograms and compare with the built-in cv2.equalizeHist .• Smooth image Synthetic.png with a box filter of size 5 and a Gaussian kernel of size 5 and a sigma of size 3. • Smooth image Building.png with a box filter of size 30 and a Gaussian kernel of size 30 and a sigma of size 10. • Apply 2D Laplace filter as described in L3 slide 25 to images Synthetic.jpg and Sharpen.jpeg and the smoothed versions from abovePast Quiz Questions: • AY2021_Quiz1 • AY2122_Quiz1: Q1 to Q4
Overview In this lab, your robot will be tasked with supervising a warehouse. The robot will have to map out its environment (using a lot of the same algorithms you have employed throughout the class), while avoiding obstacles (walls). If an obstacle is hit, the run is terminated. Your goal is to visit all of the five landmarks within 6 minutes (360 seconds). All the important files are present under the folder controllers/exploration_controller/. Specifically, focus on controllers/exploration_controller/exploration.py file. Exploration task Map Layout The map is organized as an occupancy grid, where each cell in the grid is either labeled “free”, “obstacle”, or “landmark”. In addition, every cell in the map starts out as unexplored (grey area), and as grid cells enter the robot’s field of vision, the cells are detected by the robot’s sensors and should be marked as explored. Localization Planning You will implement the frontier_planning() as well as the exploration_state_machine() functions in controllers/exploration_controller/exploration.py in order to traverse the map and visit all of the landmarks. Your frontiers are the unexplored cells in the map that are adjacent to the explored cells, and your algorithm should move to the centroid of the frontiers. Local Testing: Make sure to take advantage of functions in utils.py and remember that your run for either phase will terminate if you collide with an obstacle. Grading Rubric Autograder will grade your exploration on 10 maps. Submission Materials Submit your exploration.py file to gradescope. If you relied significantly on any external resources to complete the lab, please reference these in the submission comments. Running with Webots Once the exploration.py is complete, you can validate that your algorithm works with the WeBots simulator. 1. Open exploration_controller.py and ensure that the maze_name (line: 255) is set to the map you would like to test on. The map names are “maze1”, “maze2”, and “maze3”. A working implementation should work on all three maps. 2. Launch WeBots. Click File > Open World, then navigate to the “worlds” subfolder. Open the .wbt file which matches the maze_name from step 1. 3. A GUI window should appear which shows your exploration code running in a simple 2D approximation of the world to find a path. Then, the robot in WeBots should start moving along this path. a. We recommend selecting the “DEF e-puck Robot” object via the sidebar in the top-left of the WeBots screen. This will allow you to see the coordinate frame of the robot while it moves through the maze. b. Note that the 2D GUI window should automatically close after the robot is done moving. c. Also, the webots execution takes significantly longer time to run compared to GUI and autograder version. Examples (Robot-GUI) Robots should navigate towards the frontierRobot can use RRT to get around the obstacleBlue dot signifies the goal point Dotted line signifies the path to the next waypoint in the RRT path
LAB 5: PATH PLANNINGThe objective of this lab is to implement and test robot path planning capabilities, specifically the RRT algorithm. You will first implement the RRT algorithm, then apply it to drive a 2D robot in the WeBots simulation environment from start to goal configurations. In this lab, we assume that the obstacles and map are known ahead of time.All the code you have to implement is in the controllers/rrt_controller subfolder. Specifically, look for the files controllers/rrt_controller/map.py and controllers/rrt_controller/rrt.py.Part 1 – Basic RRTPlease complete the following helper functions in controllers/rrt_controller/map.py.• is_inbound() • is_inside_obstacle() • node_generator() • step_from_to()To test these helper functions, we have given you a local autograder. This should be much faster to run locally than on Gradescope. To run the autograder, navigate to the controllers/rrt_controller subfolder, then run python3 autograder.py helpersAfterwards, complete the RRT method in rrt.py, which handles the main loop of the algorithm. We provide code to limit the maximum number of nodes generated and terminate the loop once a path to goal has been found. Use your helper functions to implement the rest of RRT. Again, you can test this locally with python3 autograder.py rrtOnce the above steps are complete, you can validate that your RRT algorithm works with the WeBots simulator. (More detailed steps are on the next page.)1. Open rrt_controller.py and ensure that the MAP_NAME constant at the top is set to the map you would like to test on. The maps are named maze1, maze2, and maze3 (e.g. “./maps/maze2.json”). A working implementation should work on all three maps. 2. Launch WeBots. Click File > Open World, then navigate to the “worlds” subfolder. Open the .wbt file which matches the MAP_NAME from step 1. 3. A GUI window should appear which shows your RRT code running in a simple 2D approximation of the world to find a path. Then, the robot in WeBots should start moving along this path. a. We recommend selecting the “DEF e-puck Robot” object via the sidebar in the topleft of the WeBots screen. This will allow you to see the coordinate frame of the robot while it moves through the maze. b. Note that the 2D GUI window should automatically close after the robot is done moving.Figure 1. The WeBots world maze2 with the coordinate frame of the e-puck robot selected.Part 2 – Path SmoothingOnce again, you can test your implementation with the WeBots simulator, which will follow the same procedure detailed above.To test this part, you can use the same local autograder. This should be much faster to run locally than on Gradescope. To run the autograder, navigate to the controllers/rrt_controller subfolder, then run python3 autograder.py smoothingGrading: Your grade will come from the autograder running your code on the three maps you are given, plus three hidden maps which are different than the hidden ones.The exact point breakdown is as follows:Helpers is_inbound() 5 pts is_in_obstacle() 5 pts step_from_to() 10 pts Full RRT implementation RRT, autograded with 6 maps (3 hidden), 10 points per solved map 60 pts Path Smoothing Path smoothing, autograded with unsmoothed trajectories given 20 ptsSubmission: Submit the files rrt.py and map.py to Gradescope. If you relied significantly on any external resources to complete the lab, please reference these in the submission comments.
SIMULATORIn Project 4, you will implement a particle filter in the Webot simulator. It builds upon the foundation established in prior labs, emphasizing on: 1. Coordinate Transformation: To understand and implement coordinate transformations between the world frame, sensor frame, and robot frame to enable accurate localization and perception in robotics tasks. 2. Differntial Drive: To understand and implement the kinematics of a differential drive robot. 3. Detection Failure and Spurious Detection Handling: To develop strategies to address detection failures and spurious detections, ensuring reliable performance of robotic perception systems in challenging scenarios. 4. Operating in Ambiguous Environments: To explore techniques for navigating larger environments with strong ambiguity, including solving the kidnapped robot problem, to enhance adaptability and robustness in real-world robotics applications.A. Project Structure: The project directory, Project_4 contains the following files: Worlds: • simple_world.wbt:1 A simple square world for testing the particle filter. (Ref. Figure 1b)Controllers: • proj4_simple_world1_controller.py: Controls the robot to turn in-place in the center in the simple world. • proj4_maze_world1_controller.py: Controls the robot’s movement along a predefined trajectory in the maze world. Particle_filter: • contour.py: Deals with extracting contours from camera images. • geometry.py: Contains functions related to geometric calculations and transformations. • gui.py: Creates a Graphical User Interface (GUI) for visualizing the particle filter simulation. • particle_filter.py: Has the particle filter algorithm. • run_pf.py: Reads captured data in “data” folder and run particle filter without Webots simulator. • sensors.py: Contains functions related to converting sensor data for the particle filter algorithm. • setting.py: Holds various configuration settings used throughout the project. • utils.py: Contains utility functions commonly used in the project. • unit_tests.py: Contains unit tests for functions in geometry.py, environment.py. It doesn’t test the implementation of particle filter.B. General Guidance: • You will implement functions in order in geometry.py, environment.py, and particle_filter.py. • Refer to the comments in each TODO for specific implementation guidance. • Use reference lectures and additional resources for understanding the particle filter algorithm. • Utilize the provided unit tests to validate your code by running unit_tests.py. • Submit the modified files in the controller’s folder as instructed.C. Instructions Please follow these instructions carefully to ensure successful project completion. First, complete code modifications in geometry.py and environment.py: o geometry.py: transform_point(), compose(), inverse() o environment.py: read_marker_measures() and diff_drive_kinematics() Run unit_test.py to verify your implementations in geometry.py and environment.py. Ensure all test cases pass before proceeding to the next steps. This step is crucial for validating the correctness of your code modifications. When the provided test cases in unit_tests.py pass, implement functions in particle_filter.py o particle_likelihood() o compute_particle_weights() Your goal is to make the estimated robot pose as close as possible to the ground-truth robot pose. You can open the world files in “worlds” folder and run the robot controller in Webots. The robot will move along a predefined trajectory. A Python GUI will display to visualize the particles. The larger triangles represent the robot and its estimation, and the smaller triangles indicate the particle poses. The orange and purple lines in front of the robot illustrate marker measurements by cameras and lidar, respectively, and the grey dashed lines are field-of-view of the robot. The small cyan dots represent the lidar array.You can verify the particle filter convergence in one of the following ways: o Test in Webots ▪ Set DATA_CAPTURE_MODE = False in setting.py. ▪ Open a Webots world file and run the attached controller. ▪ A python GUI will show up to visualize the particles. o Capture data in Webots then run particle filters separately ▪ Set DATA_CAPTURE_MODE = True in setting.py. ▪ Open a Webots world file and run the attached controller. The captured data will be stored in the “data” folder. ▪ Change SCENARIO_NAME variable to the desired world name in run_pf.py. ▪ Run run_pf.py in particle filter. ▪ A python GUI will show up to visualize the particles.It usually takes several minutes to finish running particle filter on the maps.D. Hints for code completion: • geometry.py: o The SE2 class represents a 2D pose/transformation, incorporating both position and orientation components. o Use this class to represent the pose of a coordinate frame, perform coordinate frame transformations, and apply transformation operations to rotate and translate coordinate frames or points. o Implement methods for point transformation (transform_point), composition of transformations (compose), and inversion of transformations (inverse). • environment.py: o The read_marker_measures function generates expected ground-truth marker measurements given the pose of the robot. o Utilize coordinate transformations to compute the marker positions relative to the robot’s pose. o Remember to handle visibility checks and consider hints provided in the function comments. o Utilize the provided robot and wheel radius to convert wheel rotational speeds into linear and angular velocities for the diff_drive_kinematics function. And then, apply the kinematic equations specific to differential drive robots to calculate the forward speed and counterclockwise rotational speed based on the rotational speeds of the left and right wheels. • particle_filter.py: o The particle_likelihood function calculates the likelihood of a particle pose being the robot’s pose based on observed marker measurements. o Treat unmatched particle marker measures as detection failures and unmatched robot marker measures as spurious detections. o Utilize helper functions like generate_marker_pairs and marker_likelihood implemented in Project 3.E. Submission:F. Grading: (Total 100 points) • Geometry.py (30 points) o transform_point () – 10 points o compose () – 10 points o inverse () – 10 points • environment.py (30 points) o read_marker_measures () – 20 points o diff_drive_odometry () – 10 points • Integration test (40 points) o simple map – 15 points o maze map – 25 pointsG. Additional Notes: • Run the provided local unit tests on the simple world before proceeding to the maze world. • Ensure your implementations adhere to the specified requirements and maximize your score potential by following the instructions carefully.
Overview The setting for this project is that an e-puck robot is navigating a maze to find a traffic sign. You are provided code that will determine whether the traffic sign is in the camera feed of the robot. Your task will be to determine: 1. The depth (not the distance) and angle to the sign using the 2-cameras method 2. The distance and angle to the sign using camera+lidar method In the second part, you will leverage the lidar on the robot to determine the distance and heading, using both the point cloud of the lidar, and one image captured by the robot. The lidar data is composed of an array of 360 distance values around the robot, one for each degree for 0 to 359 deg.Webots Simulator We will be employing the Webots simulator in this project (and in some of the future projects in this course). You will need to install it using the following installation procedure (this includes documentation for Linux, Windows, and Mac). You will be provided with a series of world files and a controller for the e-puck robot. The assignment will then require finding the distance/depth and heading of a traffic sign, relative to the robot, in each world file. The code structure and respective functions is described in the next section. To test out your scripts in the Webots simulator, open a world file (named either as proj2_world_vision_lidar_#.wbt or as Vision_only_world#.wbt), and run the simulation. The first few (typically 3) iterations running the controller might have blank images, however it should then allow you to see the required distance/ depth and angle values print on the Webots console.Requirements Installation You can use the requirements.txt file to install all necessary packages by running pip install -r requirements.txtAssignment Preliminaries The field of view is the range of the world (in this project, defined in radians) in the horizontal plane that is visible.We provide the following formula that can be used to include the field of view in the calculation of focal length for both parts 1 and 2. focal_length = image_width / (2 * math.tan(fov / 2))Part 1: Determine depth and angle using stereo vision To complete part 1, you will need to fill out the vision_only_depth_calculation(image1, image2, fov, camera_translation) function in proj2_vision_only_controller/vision_only_calculation.py The vision_only_depth_calculation(image1, image2, fov, camera_translation) function takes in two images, camera field of view, camera translation (distance between the 2 cameras) and returns the depth (perpendicular distance from the traffic sign to the line joining the cameras) and angle from the robot to the traffic sign in the images.Hint: try using trigonometry to calculate the angle, using the parameters mentioned in the diagram above.Part 2: Determine distance and angle using vision and lidar To complete part 2, you will need to fill out the vision_lidar_distance_calculation(image, lidar_range_array, fov) function in proj2_vision_lidar_controller/vision_lidar_calculation.py The vision_lidar_distance_calculation(image, lidar_range_array, fov) function takes in an image and the point cloud returned from a lidar, and returns the distance and angle from the robot to the traffic sign in the images.Functions Provided To complete the above two parts, you are provided with the contour.py file, which contains a function box_measure(image) that calculates the pixel values of the centroid of the identified traffic sign in the image. This file (identical copies) can be found in both the proj2_vision_lidar_controller and the proj2_vision_only_controller folders. Submission Instructions The files you will submit to Gradescope are vision_lidar_calculation.py and vision_only_calculation.py To test your solution locally, you can employ the provided local_tests.py files.– NumPy – OpenCVRubric for Vision Component Your solution for part 1 (stereo vision) will be evaluated in 5 world files. Each world will be worth 10 points for a total of 50 points possible. Depth Evaluation For each world, you will receive a number of points based upon how close your detected depth is from the true depth. The difference between your depth and the true depth will be evaluated as a percentage of the true depth. For example, if the true depth is 10 cm and you say that the depth is 9 cm, then the difference is 1 cm. This is 10% of the true 10 cm, so the grade would be 8 out of 10 for that world file. Percentage difference in distance Point Count
IntroductionIn this project you will be implementing neural nets, and in particular the most common algorithm for learning the correct weights for a neural net from examples. Code structure is provided for a Perceptron and a multi layer NeuralNet class, and you are responsible for filling in some missing functions in each of these classes. This includes writing code for the feed forward processing of input, as well as the backward propagation algorithm to update network weights.Files you will editNeuralNet.py: Your entire Neural Net implementation will be within this file Testing.py: Helper functions for learning a neural net from data NeuralNet_report.pptx: Your answers to the analysis questions go into this file. Convert this file to a pdf and then submit it to Gradescope. You must submit your written answers in this format. Do not remove or add slides. (optional) xor.txt: Your training examples for q7 (extra credit) (optional) NeuralNetUtil.py: Functions for converting the datasets into python data structures Testing.py Helper functions for learning a neural net from data. Note: if you decide to do question 8 for extra credit, you will have to add a method to this file.EvaluationYour code will be autograded for technical correctness, using the same autograder and test cases you are provided with. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. You should ensure your code passes all the test cases before submitting the solution, as we will not give any points for a question if not all the test cases for it pass. However, the correctness of your implementation, not the autograder’s judgments, will be the final judge of your score. Even if your code passes the autograder, we reserve the right to check it for mistakes in implementation, though this should only be a problem if your code takes too long or you disregarded announcements regarding the project. The short answer grading guidelines are explained below.Getting HelpNeural Network Learning ImplementationThis project follows the same terminology as in the lectures and Ch 18.7 in your book. Neural networks are composed of nodes called perceptrons, as well as input units. Every perceptron has inputs with associated weights, and from this it produces an output based on its activation function. Thus you will be implementing a feed forward multi layer neural net.We will be training the neural nets to be classifiers. Inputs will be in the form of sets of examples that have an assignment of values to various features and corresponding class values. The datasets used for this project include a cars dataset and a dataset of pen handwriting values. For the latter, numeric data from images is stored to train a classifier of handwritten digits.The code we provide you has the methods for parsing the datasets into python data structures, and the beginning of the Perceptron and NeuralNet classes. A Perceptron merely stores an input size and weights for all the inputs, as well as methods for computing the output and error given an input. An object of the NeuralNet class stores lists of Perceptrons and has methods for computing the output of an entire network and updating the network via back propagation learning. The network consists of inputs (just a list of inputs that is a parameter to feed forward), an output layer, and 0 or more hidden layers. Although the structure and initialization is written, all the actual functionality will be implemented by you. Question 1 (2 points): Feed ForwardImplement sigmoid and sigmoidActivation in the Perceptron class. Then, implement feedForward in the NeuralNet class. Be sure to heed the comments in particular, don’t forget to add a 1 to the input list for the bias input. You now have a Neural Net classifier! However, the weights are still randomized so it is rather useless…File you’ll edit: NeuralNet.py Question 2 (2 points): Weight UpdateImplement sigmoidDeriv, sigmoidActivationDeriv, and updateWeights in Perceptron according to the equation in the book. Note that delta is an input to updateWeights, and will be the appropriate delta value regardless of whether the Perceptron is in the output or a hidden layer; its computation will be implemented later in backPropLearning.File you’ll edit: NeuralNet.py Question 3 (4 points): Back Propagation LearningFor test backprop0.test, the deltas for the first iteration are:[[0.030793495980775746, 0.015482381603395969, 0.011581614293905421, 0.004449919337742824, 0.02164433012587241, 0.02929895427882054, 0.009128354470904964, 0.002752718694772222, 0.0136716072376759, 0.015406354991598608, 0.013100536741508734, 0.0041637660666657295, 0.00017176192932002172, 0.010111421606106267, 0.036790975475881824, 0.007334760193359876, 0.00698074822965782, 0.029598447675293165, 0.010824328898999185, 0.03097345080247739, 0.007777081314307609, 0.0023536881454502725, 0.01345707648774709, 0.007920771403715898], [ 0.026000590890107898, 0.06031387251323732, 0.03958313495848832, 0.07355044647726003, 0.06973954192905674, 0.10235871158610363, 0.13274639952200898, 0.11272791158412912, 0.0627102923404577, 0.03676930932503297]]File you’ll edit: NeuralNet.py Question 4 (4 points): Back Propagation Learning LoopLastly, implement buildNeuralNet to actually train a good neural network classifier. The stopping condition for training should be the average weight modification of all edges going below the passed in threshold, or the iteration going above the maximum number of iterations also passed in. See the comments in the code for more detail. You should now have a working neural net classifier! If your solutions are right, then calling testPenData in Testing.py should result in output similar (since we are starting from random weights, the numbers will not be exactly the same) to this:Starting training at time 01:17:58.806009 with 16 inputs, 10 outputs, hidden layers [24], size of training set 7494, and size of test set 3498. . . . . . . . . ! on iteration 10; training error 0.006085 and weight change 0.000272 . . . . . . . . . ! on iteration 20; training error 0.004340 and weight change 0.000188 . . . . . . . . . ! on iteration 30; training error 0.003674 and weight change 0.000144 . . . . . . . . . ! on iteration 40; training error 0.003342 and weight change 0.000119 . . . . . . . . . ! on iteration 50; training error 0.003142 and weight change 0.000102 . . . . . . . . . ! on iteration 60; training error 0.003006 and weight change 0.000091 . . . . . . . . . ! on iteration 70; training error 0.002902 and weight change 0.000083 . . . ! on iteration 74; training error 0.002865 and weight change 0.000080Finished after 74 iterations at time 01:25:13.266676 with training error 0.002865 and weight change 0.000080Feed Forward Test correctly classified 3118, incorrectly classified 380, test accuracy 0.891366File you’ll edit: NeuralNet.pyAnalysisPut your answers to questions 5-8 in NeuralNet_report.pptx with data tables and plots, with a short and concise written analysis for each question. We primarily care that you report the performance statistics asked for accurately. You will convert your slides to PDF later on for submission.Question 5 (4 points): Learning with RestartsFile you’ll edit: NeuralNet_report.pptx Question 6 (4 points): Varying the Hidden LayerVary the amount of perceptrons in the hidden layer from 0 to 40 inclusive in increments of 5, and get the max, average, and standard deviation of 5 runs of testPenData (you’ll want just let your computer run this one for a while) and testCarData for each number of perceptrons. Report the results in a table. Additionally, produce a learning curve with the number of hidden layer perceptrons being the independent variable and the average accuracy being the dependent variable. Briefly discuss any notable trends you noticed related to increasing the size of the hidden layer has in your neural net. You should write your own code that uses the functions of Testing.py and NeuralNet.py to do this.File you’ll edit: NeuralNet_report.pptxExtra Credit Question 7 (2 points Extra Credit): Learning XORAs you’ve learned in class, adding the hidden layer allows Neural Nets to learn non linear functions such as xor. To show this in effect, produce the set of examples needed to train a Neural Net to compute a 2 variable xor function. Put your examples in a text file called xor.txt. Train a neural net without a hidden layer with it and report the behavior. Then, run it on neural nets starting with 1 perceptron in the hidden layer and increasing until you get a neural net that works well. Are the results what you expected? File you’ll edit: NeuralNet_report.pptx Question 8 (2 points Extra Credit): Novel DatasetExplore the UCI Machine Learning Repository or other ML datasets found online, and select a new dataset to try your Neural Network with. Write a method in NeuralNetUtil.py called buildExamplesFromExtraData that is akin to the other get methods we wrote. Answer question 5 for this dataset, and submit your NeuralNetUtil.py in addition to NeuralNet.py for the option of extra credit. Also include your code to set up training and a description on how to run this code.File you’ll edit: NeuralNet_report.pptx, NeuralNetUtil.pySubmissionMake sure to convert NeuralNet_report.pptx to a PDF. Do NOT add or remove slides.Programming Files: • NeuralNet.py • xor.txt (optional for question 7) • NeuralNetUtil.py (optional for question 8)Non-programming Files: • NerualNet_report.pdfPyPy“If you want your code to run faster you should probably just use PyPy.” – Guido van Rossum (creator of Python) What is PyPy?PyPy is an implementation of Python different than the “default” implementation you have been using all this time, which is CPython, this means that PyPy has a different way of interpreting your .py source code and executing it.The specific reasons why PyPy is so much faster than CPython is beyond the scope of this class so we won’t get much in detail apart from saying Pypy uses “just-in-time compilation”, meaning it compiles the code as it is executing it instead of simply interpreting the instructions on a script as it goes. If you’re interested in understanding more about the backend reasons for this difference the Wikipedia page for PyPy is a good starting point for you to start poking around the hyperlinks to all these concepts. How do I use Pypy?First install it directly from the source: https://www.pypy.org/download.html Once you install PyPy for your OS you can use it to run Python source code by typing: pypy filename.pyinstead of the usual: py filename.pyNote that to use PyPy to run the code for your analysis questions you do not have to change anything in NeuralNet.py or Testing.py, and you don’t have to write code any differently than “regular” Python for this to work!Just write the code for your project like you would normally do, and run the PyPy command for your files!Do I have to use PyPy for this project?
All those colored walls, Mazes give Pacman the blues, So teach him to search. Introduction In this project, your Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. You will build general search algorithms and apply them to Pacman scenarios. As in all future projects, this project includes an autograder for you to grade your answers on your machine. This can be run with the command: python autograder.py See more on using the autograder, run python autograder.py -h The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore. You are provided all the code and supporting files in the zip of this assignment. Files you’ll edit: search.py Where all of your search algorithms will reside. searchAgents.py Where all of your search-based agents will reside. Files you might want to look at: pacman.py The main file that runs Pacman games. This file describes a Pacman GameState type, which you use in this project. game.py The logic behind how the Pacman world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid. util.py Useful data structures for implementing search algorithms. Supporting files you can ignore: graphicsDisplay.py Graphics for Pacman graphicsUtils.py Support for Pacman graphics textDisplay.py ASCII graphics for Pacman ghostAgents.py Agents to control ghosts keyboardAgents.py Keyboard interfaces to control Pacman layout.py Code for reading layout files and storing their contents autograder.py Project autograder testParser.py Parses autograder test and solution files testClasses.py General autograding test classes test_cases/ Directory containing the test cases for each question searchTestClasses.py Project 1 specific autograding test classes Files to Edit and Submit: You will fill in portions of search.py and searchAgents.py during the assignment. You should submit these files with your code and comments. Please do not change the other files in this distribution or submit any of our original files other than these files. You will not need to zip your submission. Evaluation: Your code will be autograded for technical correctness, using the same autograder and test cases you are provided with. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. You should ensure your code passes all the test cases before submitting the solution, as we will not give any points for any questions if not all the test cases for it pass. However, the correctness of your implementation — not the autograder’s judgements — will be the final judge of your score. Even if your code passes the autograder, we reserve the right to check it for mistakes in implementation, though this should only be a problem if your code takes too long or you disregarded announcements regarding the project. Imports: Do NOT import any new libraries for this project (ie. numpy, scikit learn, pandas, etc). Some of these libraries trivialize the assignment and importantly they are not installed on the gradescope autograder. Importing these libraries will crash the autograder and that submission will recieve a zero. Please also check that your IDE did not incidentally import libraries (common with VSCode for instance). See more in the debugging gradescope section. Welcome to Pacman After unzipping the code and changing to its directory, you should be able to play a game of Pacman by typing the following at the command line: python pacman.py Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman’s first step in mastering his domain. The simplest agent in searchAgents.py is called the GoWestAgent, which always goes West (a trivial reflex agent). This agent can occasionally win: python pacman.py –layout testMaze –pacman GoWestAgent But, things get ugly for this agent when turning is required: python pacman.py –layout tinyMaze –pacman GoWestAgent If Pacman gets stuck, you can exit the game by typing CTRL-c into your terminal. Soon, your agent will solve not only tinyMaze, but any maze you want. Note that pacman.py supports a number of options that can each be expressed in a long way (e.g., –layout) or a short way (e.g., -l). You can see the list of all options and their default values via: python pacman.py -h Also, all of the commands that appear in this project also appear in commands.txt, for easy copying and pasting. In UNIX/Mac OS X, you can even run all these commands in order with bash commands.txt. Note: if you get error messages regarding Tkinter, see this page Object Glossary Here’s a glossary of the key objects in the code base related to search problems, for your reference: SearchProblem (search.py) A SearchProblem is an abstract object that represents the state space, successor function, costs, and goal state of a problem. You will interact with any SearchProblem only through the methods defined at the top of search.py PositionSearchProblem (searchAgents.py) A specific type of SearchProblem that you will be working with — it corresponds to searching for a single pellet in a maze. CornersProblem (searchAgents.py) A specific type of SearchProblem that you will define — it corresponds to searching for a path through all four corners of a maze. FoodSearchProblem (searchAgents.py) A specific type of SearchProblem that you will be working with — it corresponds to searching for a way to eat all the pellets in a maze. Search Function A search function is a function which takes an instance of SearchProblem as a parameter, runs some algorithm, and returns a sequence of actions that lead to a goal. Example of search functions are depthFirstSearch and breadthFirstSearch, which you have to write. You are provided tinyMazeSearch which is a very bad search function that only works correctly on tinyMaze SearchAgent SearchAgent is a class which implements an Agent (an object that interacts with the world) and does its planning through a search function. The SearchAgent first uses the search function provided to make a plan of actions to take to reach the goal state, and then executes the actions one at a time. Finding a Fixed Food Dot using Search Algorithms In searchAgents.py, you’ll find a fully implemented SearchAgent, which plans out a path through Pacman’s world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented — that’s your job. As you work through the following questions, you might find it useful to refer to the object glossary (the second to last tab in the navigation bar above). First, test that the SearchAgent is working correctly by running: python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm, which is implemented in search.py. Pacman should navigate the maze successfully. Important note: All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls). Important note: Make sure to use the Stack, Queue and PriorityQueue data structures provided to you in util.py! These data structure implementations have particular properties which are required for compatibility with the autograder. Hint: Each algorithm is very similar. Algorithms for DFS, BFS, UCS, and A* differ only in the details of how the fringe is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit). Question 1 (2 points) Implement the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py. To make your algorithm complete, write the graph search version of DFS, which avoids expanding any already visited states. Your code should quickly find a solution for: python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent python pacman.py -l bigMaze -z .5 -p SearchAgent The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal? Hint: If you use a Stack as your data structure, the solution found by your DFS algorithm for mediumMaze should have a length of 130 (provided you push successors onto the fringe in the order provided by getSuccessors; you might get 246 if you push them in the reverse order). Is this a least cost solution? If not, think about what depth-first search is doing wrong. Question 2 (2 points) Implement the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py. Again, write a graph search algorithm that avoids expanding any already visited states. Test your code the same way you did for depth-first search. python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5 Does BFS find a least cost solution? If not, check your implementation. Hint: If Pacman moves too slowly for you, try the option –frameTime 0. Note: If you’ve written your search code generically, your code should work equally well for the eight-puzzle search problem without any changes. python eightpuzzle.py Varying the Cost Function While BFS will find a fewest-actions path to the goal, we might want to find paths that are “best” in other senses. Consider mediumDottedMaze and mediumScaryMaze. By changing the cost function, we can encourage Pacman to find different paths. For example, we can charge more for dangerous steps in ghost-ridden areas or less for steps in food-rich areas, and a rational Pacman agent should adjust its behavior in response. python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs python pacman.py -l mediumDottedMaze -p StayEastSearchAgent python pacman.py -l mediumScaryMaze -p StayWestSearchAgent Note: You should get very low and very high path costs for the StayEastSearchAgent and A* search Question 4 (3 points) Implement A* graph search in the empty function aStarSearch in search.py. A* takes a heuristic function as an argument. Heuristics take two arguments: a state in the search problem (the main argument), and the problem itself (for reference information). The nullHeuristic heuristic function in search.py is a trivial example. You can test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic (implemented already as manhattanHeuristic in searchAgents.py). python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic Finding All the Corners The real power of A* will only be apparent with a more challenging search problem. Now, it’s time to formulate a new problem and design a heuristic for it. In corner mazes, there are four dots, one in each corner. Our new search problem is to find the shortest path through the maze that touches all four corners (whether the maze actually has food there or not). Note that for some mazes like tinyCorners, the shortest path does not always go to the closest food first! Hint: the shortest path through tinyCorners takes 28 steps. Question 5 (2 points) Note: Make sure to complete Question 2 before working on Question 5, because Question 5 builds upon your answer for Question 2. Implement the CornersProblem search problem in searchAgents.py. You will need to choose a state representation that encodes all the information necessary to detect whether all four corners have been reached. Now, your search agent should solve: python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem To receive full credit, you need to define an abstract state representation that does not encode irrelevant information (like the position of ghosts, where extra food is, etc.). In particular, do not use a Pacman GameState as a search state. Your code will be very, very slow if you do (and also wrong). Hint: The only parts of the game state you need to reference in your implementation are the starting Pacman position and the location of the four corners. Our implementation of breadthFirstSearch expands just under 2000 search nodes on mediumCorners. However, heuristics (used with A* search) can reduce the amount of searching required. Question 6 (3 points) Note: Make sure to complete Question 4 before working on Question 6, because Question 6 builds upon your answer for Question 4. Implement a non-trivial, consistent heuristic for the CornersProblem in cornersHeuristic.Project 1.htm python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5 Note: AStarCornersAgent is a shortcut for -p SearchAgent -a fn=aStarSearch,prob=CornersProblem,heuristic=cornersHeuristic. Admissibility vs. Consistency: Remember, heuristics are just functions that take search states and return numbers that estimate the cost to a nearest goal. More effective heuristics will return values closer to the actual goal costs. To be admissible, the heuristic values must be lower bounds on the actual shortest path cost to the nearest goal (and non-negative). To be consistent, it must additionally hold that if an action has cost c, then taking that action can only cause a drop in heuristic of at most c. Remember that admissibility isn’t enough to guarantee correctness in graph search — you need the stronger condition of consistency. However, admissible heuristics are usually also consistent, especially if they are derived from problem relaxations. Therefore it is usually easiest to start out by brainstorming admissible heuristics. Once you have an admissible heuristic that works well, you can check whether it is indeed consistent, too. The only way to guarantee consistency is with a proof. However, inconsistency can often be detected by verifying that for each node you expand, its successor nodes are equal or higher in f-value. Moreover, if UCS and A* ever return paths of different lengths, your heuristic is inconsistent. This stuff is tricky! Non-Trivial Heuristics: The trivial heuristics are the ones that return zero everywhere (UCS) and the heuristic which computes the true completion cost. The former won’t save you any time, while the latter will timeout the autograder. You want a heuristic which reduces total compute time, though for this assignment the autograder will only check node counts (aside from enforcing a reasonable time limit). Note: You cannot use the mazeDistance function for this question. Grading: Your heuristic must be a non-trivial non-negative consistent heuristic to receive any points. Make sure that your heuristic returns 0 at every goal state and never returns a negative value. Depending on how few nodes your heuristic expands, you’ll be graded: Number of nodes expanded Grade more than 2000 0/3 at most 2000 1/3 at most 1600 2/3 at most 1200 3/3 Remember: If your heuristic is inconsistent, you will receive no credit, so be careful! Eating All The Dots Now we’ll solve a hard search problem: eating all the Pacman food in as few steps as possible. For this, we’ll need a new search problem definition which formalizes the food-clearing problem: FoodSearchProblem in searchAgents.py (implemented for you). A solution is defined to be a path that collects all of the food in the Pacman world. For the present project, solutions do not take into account any ghosts or power pellets; solutions only depend on the placement of walls, regular food and Pacman. (Of course ghosts can ruin the execution of a solution! We’ll get to that in the next project.) If you have written your general search methods correctly, A* with a null heuristic (equivalent to uniform-cost search) should quickly find an optimal solution to testSearch with no code change on your part (total cost of 7). Project 1.htm python pacman.py -l testSearch -p AStarFoodSearchAgent Note: AStarFoodSearchAgent is a shortcut for -p SearchAgent -a fn=astar,prob=FoodSearchProblem,heuristic=foodHeuristic. You should find that UCS starts to slow down even for the seemingly simple tinySearch. As a reference, our implementation takes 2.5 seconds to find a path of length 27 after expanding 5057 search nodes. Question 7 (4 points) Note: Make sure to complete Question 4 before working on Question 7, because Question 7 builds upon your answer for Question 4. Fill in foodHeuristic in searchAgents.py with a consistent heuristic for the FoodSearchProblem. Try your agent on the trickySearch board: python pacman.py -l trickySearch -p AStarFoodSearchAgent Our UCS agent finds the optimal solution in about 13 seconds, exploring over 16,000 nodes. Any non-trivial non-negative consistent heuristic will receive 1 point. Make sure that your heuristic returns 0 at every goal state and never returns a negative value. Depending on how few nodes your heuristic expands, you’ll get additional points:Remember: If your heuristic is inconsistent, you will receive no credit, so be careful! Can you solve mediumSearch in a short time? If so, we’re either very, very impressed, or your heuristic is inconsistent. Again, you cannot use the mazeDistance function for this question. Suboptimal Search Sometimes, even with A* and a good heuristic, finding the optimal path through all the dots is hard. In these cases, we’d still like to find a reasonably good path, quickly. In this section, you’ll write an agent that always greedily eats the closest dot. ClosestDotSearchAgent is implemented for you in searchAgents.py, but it’s missing a key function that finds a path to the closest dot. Question 8 (2 points) Implement the function findPathToClosestDot in searchAgents.py. Our agent solves this maze (suboptimally!) in under a second with a path cost of 350: python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5 Project 1.htm Hint: The quickest way to complete findPathToClosestDot is to fill in the AnyFoodSearchProblem, which is missing its goal test. Then, solve that problem with an appropriate search function. The solution should be very short! Your ClosestDotSearchAgent won’t always find the shortest possible path through the maze. Make sure you understand why and try to come up with a small example where repeatedly going to the closest dot does not result in finding the shortest path for eating all the dots. Mini Contest (up to 2 points extra credit) Implement an ApproximateSearchAgent in searchAgents.py that finds a short path through the bigSearch layout. If your agent finds a solution of cost at most 290 receive you 1 point extra credit. If the cost is at most 280 you receive 2 points extra credit. python pacman.py -l bigSearch -p ApproximateSearchAgent -z .5 -q We will time your agent using the no graphics option -q, and it must complete in under 30 seconds on our grading machines. Please describe what your agent is doing in a comment! Don’t hard-code the path, of course. There is a mazeDistance helper function that you can use if you need to. This function finds the distance between two coordinates, accounting for walls. Debugging Gradescope: At this point you’re ready to submit and the local autograder is working! You upload to gradescope and hopefully you see the exact same score you saw locally. But sometimes you’ll see something like this:9 times out of 10 this is an issue of imports. Check your imports in searchAgents.py They should look like: from game import Directions from game import Agent from game import Actions import util import time import search Check your imports in search.py They should look like: import util The 1 time out of 10 it’s because you used some sort of obscure python feature that the autograder can’t handle. You can check what’s new in python here. If neither of these issues seem to be your case you might’ve found a corner case from what we’ve seen before!
1 Introduction The goal of the final project is to implement two kinds of model-free RL methods: value-based RL and policy-based RL. In this project, you are free to choose RL methods to solve two benchmark environments. 2 Review 2.1 Value-Based Reinforcement Learning Value-based methods strive to fit action value function or state value function, e.g. Monte-Carlo, TD learning for model-free policy evaluation and SARSA, Qlearning for model-free control. Off-policy training mode is easy to implement in value-based method. DQN achieves remarkable performance under off-policy. In DQN (Silver, 2015), past experiences that stored in experience buffer can be used to train the deep Q network. In many transfer algorithms for DQN, expert’s experiences are often used to fit the current value function. Hence value-based methods are often more sample efficient. Although value-based RL like DQN and its variants achieve remarkable performance in some task, e.g. atari games, the inherent drawbacks hinder its development. • First, action selection in value-based methods is according to the action values, which is inherently unsuited to continuous action space. • Second, non-linear value function approximation like neural network is unstable and brittle with respect to their hyperparameters. 2.2 Policy-Based Reinforcement Learning 3 Experiment Environments and Requirements OpenAI provides benchmark environments toolkit ‘gym’ to facilitate the development of reinforcement learning. 6 types of experiment environments are available (access https://www.gymlibrary.dev/ for more). In our project, you are required to train agents over Atari and MuJuCo. You should choose appropriate and effective RL methods to achieve high scores in the environments as possible as you can. To get started with gym, refer to https://github.com/ openai/gym. 3.1 Atari Games Environment Description The Atari 2600 is a home video game console developed in 1977. Dozens of games are provided by ‘gym’. In our project, we limit the choice of environment to the following: • VideoPinball-ramNoFrameskip-v4 • BreakoutNoFrameskip-v4 • PongNoFrameskip-v4 • BoxingNoFrameskip-v4 You should at least choose one environment to test your value-based method. 3.2 MuJuCo Continuous Control Environment Description MuJuCo stands for Multi-Joint dynamics with Contact, which is originally designed for model-based control methods test. Now, MuJoCo simulator is a commonly adopted benchmark for continuous control. We narrow down the choice of environments to the following: • Hopper-v4 • Humanoid-v4 • HalfCheetah-v4 • Ant-v4 You should at least choose one environment to test your policy-based method. 3.3 Requirements Here is the experiment content: • You are required to choose and implement value-based RL algorithm and test it on at least one of the Atari game listed above. • You are required to choose and implement policy-based RL algorithm (except Soft Actor-Critic) and test it on at least one of the MuJuCo simulator listed above. The algorithms you choose in the scope of value-based and policy-based are non-limited. For the ease of running your submitted codes and grading, we have some limitations in this project. • Programming language: python3 • The final results should use the experiment Name like following: python run.py –env name BreakoutNoFrameskip-v4 4 Report and Submission 4.1 About Submission • You are required to accomplish this project individually. • Your report and source code should be zipped and named after ”Name StuID”. Besides, README file that shows the instructions to run your code should be included inside the zip file. 4.2 About Report The report should cover but not be limited to the following sections: • The description of the algorithms you use. • The performance of the algorithms you achieve in selected environments • The analysis about the algorithms. 4.3 Bonus • Modification of the algorithms that achieves better performance. • Test your algorithms on more than one environment. • Excellent analysis about the algorithms.
1 Introduction 2 Actor-Critic Algorithm In original policy gradient 5θlogπθ(st,at)vt, return vt is the unbiased estimation of expected long-term value Qπθ(s,a) following a policy πθ(s) (Actor). However, original policy gradient suffers from high variance. Actor-Critic Algorithm uses Q value function Qw(s,a), named Critic, to estimate Qπθ(s,a). DDPG borrows the success from DQN by introducing experience replay and target Q network into deterministic policy gradient method (DPG). DPG deterministically maps states to specific action instead of outputting a stochastic policy over all actions. In A3C, we maintain several instances of local agent and a global agent. Instead of experience replay, we asynchronously execute all the local agents in parallel. The parameter of the global agent is updated by all the local experience. The pseudo code is listed at the end of the article. For more details of these two algorithms, you can refer to the original papers in the following. • Lillicrap T P, Hunt J J, Pritzel A, et al. Continuous control with deep reinforcement learning[J]. arXiv preprint arXiv:1509.02971, 2015. 3 Experiment Description • Programming language: python3 • You are required to implement A3C and DDPG algorithms. • You should test your agent in a classical RL control environment–Pendulum. OPENAI gym provides this environment, which is implemented with python (https://www.gymlibrary.dev/environments/classic_control/pendulum/). You can also refer to gym’s source code at (https://github.com/openai/ gym). 4 Report and Submission • Your report and source code should be compressed and named after “studentID+name+assignment5”.
1 Introduction The goal of this assignment is to do experiment with deep Q network (DQN), which combines the advantage of Q-learning and the neural network. In classical Q-learning methods, the action value function Q is intractable with the increase of state space and action space. DQN introduces the success of deep learning and has achieved a super-human level of play in atari games. Your goal is to implement the DQN algorithm and its improved algorithm and play with them in some classical RL control scenarios. 2 Deep Q-learning Algorithm 1: deep Q-learning with experience replay. Initialize replay memory D to capacity N Initialize action-value function Q with random weights h Initialize target action-value function Q^ with weights h25h For episode 5 1, M do Initialize sequence s1~f gx1 and preprocessed sequence w1~wð Þs1 For t5 1,T do With probability e select a random action at otherwise select at~argmaxaQðwð Þst ,a;hÞ Execute action at in emulator and observe reward rt and image xt11 Set stz1~st,at,xtz1 and preprocess wtz1~wðstz1Þ Store transition wt,at,rt,wtz1 in D Sample random minibatch of transitions wj,aj,rj,wjz1 from D rj if episode terminates at step jz1 Setyj~rjzc maxa0 Q^ wjz1,a0;h{ otherwise 2 Perform a gradient descent step on yj{Q wj,aj;h with respect to the network parameters h Every C steps reset Q^~Q End For End For Figure 1: Deep Q-learning with experience replay You can refer to the original paper for the details of the DQN. “Human-level control through deep reinforcement learning.” Nature 518.7540 (2015): 529. 3 Experiment Description • Programming language: python3 • You should compare the performance of DQN and one kind of improved DQN and test them in a classical RL control environment–MountainCar. OPENAI gym provides this environment, which is implemented with python (https://gym.openai.com/envs/MountainCar-v0/). What’s more, gym also provides other more complex environment like atari games and mujoco. Since the state is abstracted into car’s position, convolutional layer is not necessary in our experiment. You can get started with OPENAI gym refer to this link (https://gym.openai.com/docs/). Note that it is suggested to implement your neural network on the Tensorflow or Pytorch. 4 Report and Submission • Your report and source code should be compressed and named after “studentID+name+assignment4”.
Programming Assignment 1 – Working of a Lexical Analyzer The objective of this assignment is to gain a hands-on experience with: 1. A version control system such as Git, 2. Make and makefiles 3. Using a lexical analyzer generator such as Flex. 1 Version Control Systems and Git Have you ever spent hours writing code (or a term paper) only to realize, when your computer crashes, that you haven’t saved your progress? Have you ever spent an hour making a change to a program only to realize that all your changes were wrong and you had to go back to the way the code was? Version control helps solve these problems. Every non-trivial program is written in stages. To write a good program, you need to divide it into stages and finish one stage at a time. After you finish one stage, commit a version so that you have a record. Version control provides many advantages. One of them is a simple way to back up your code. If, for any reason, you want to go back to a previous version, it is very easy. Version control does many more things than backing up your code. Please understand that you must commit changes often if you want to use version control. If you do not commit, version control cannot help you. This class uses git for version control. Git is a distributed version control system. That means there are two repositories: local and remote. When you commit changes, only the local repository is changed. This makes commits fast and independent of network connections. If your computer is damaged, you still lose the local repository. To make changes to the remote repository, you need to push the changes done on the local repository. If your computer is damaged, you can retrieve the code from the remote repository. Please remember that you must commit and push often to take advantage of version control. Resources that help you to get familiar with version control and Git are here and here. 1.1 Prerequisites Create a Github account (if you do not already have one). This is the account you should use to create and submit all of your assignments this semester. 1.2 Git – setup The Git setup and submission instructions remain the same for all assignments. Please replace the assignment number in the examples with the number of the assignment you are submitting. 1. Create a Git repository for the assignment. (a) Log in to your Github account. (b) Visit the Github Teams Discussion page to find the link for the assignment PA1. Click the link. This will create a repository on Github for the assignment (you will follow a similar procedure for all future assignments). Make sure that the repository is called ‘IITDhCSE/PA1-’. (c) Clone the repository to develop your assignment. Cloning a repository creates a local copy. Change your directory to whichever directory you want to create your local copy in, and type: > git clone [email protected]:IITDhCSE/PA1-.git PA1 This will create a subdirectory called PA1, where you will work on your code. In this command: git clone copies a repository. [email protected]:IITDhCSE/PA1-.git tells git where the server (remote copy) of your code is. PA1 tells git to place the code in a local directory named PA1 If you change to directory PA1 and list the contents, you should see the files you will need for this assignment: > cd PA1 > ls And you should see all of the files required to get started with this assignment. Setting up SSH key with GitHub Set up a public SSH key in your GitHub account (if you haven’t already). To do this, first generate a new ssh key: > ssh-keygen Hit enter three times (to accept the default location, then to set and confirm an empty passphrase). This will create two files: /.ssh/id_rsa (your private key) and /.ssh/id_rsa.pub (your public key) Then print out your public key: > cat /.ssh/id_rsa.pub And copy it to the clipboard. Then follow steps at: https://help.github.com/en/articles/addinga-new-ssh-key-to-your-github-account 2. As you develop your code, you can commit a local version of your changes (just to make sure that you can back up if you break something) by typing: > git add > git commit -m “< describe your changes>” git add tells git to “stage” a file for committing. Staging files is useful if you want to make changes to several files at once and treat them as one logical change to your code. You need to call git add every time you want to commit a file that you have changed. git commit tells git to save a new version of your code including all the changes you staged with git add. Note that until you execute git commit, none of your changes will have a version associated with them. You can save/commit the changes many times. It is a good habit committing often. It is very reasonable if you commit every ten minutes (or more often). 3. The changes you saved by executing git commit in the previous step are local to your development environment i.e. they are saved in a local repository. To copy your changes back to Github (to make sure they are saved if your computer crashes, or if you want to continue developing your code from another machine, or you want to make your code visible to a collaborator), type > git push If you do not push, the teaching staff cannot see your solutions. 2 Write a Makefile Makefiles let you define complicated sets of commands to build your projects. Makefiles consist of a series of rules: [target] : [dependences] [TAB] command 1 [TAB] command 2 … A rule target is the name of the rule. The dependences are the files the rule depends on. The commands are what to do when the rule is “fired”. Note: there must be a tab before each command. A rule is fired in one of two ways: (i) it is directly invoked (by calling “make [target]”) or (ii) it is invoked by another rule that is fired. When a rule is fired, it goes through the following process: 1. If a dependence has a rule in the Makefile, fire that rule (using this same process) You can use Makefiles to orchestrate complicated build processes. If you type “make” without a target, make will fire the first rule in the Makefile. We usually define a target called “clean” whose job it is to clean up any intermediate files generated during the build process. This can also be used to remove all generated targets to force recompiling everything. Makefiles also let you define macros to reuse the same commands over and over. For example, we can define GCC as a macro that invokes gcc the way we want: DEBUG = -DDEBUG CFLAGS = CFLAGS = -std=c99 -g -Wall -Wshadow –pedantic -Wvla -Werror GCC = gcc $(CFLAGS) $(DEBUG) Note that we use $(MACRO_NAME) to insert the macro into other places, including commands. Makefiles can get much more complicated than this, but their full power is beyond the scope of this course. Edit the Makefile given to you in the main directory of your repository (we will be using the Makefile to drive the building and testing process of all of your code. Create a target called dev that first prints out your name: 1. Full name (first and last) 2. IITDh email ID make dev it would print the following: Nikhil Hegde nikhilh@iitdh . ac . in 3 Scanner The working of a scanner—sometimes called the tokenizer or lexical analyzer—forms the first phase of the compilation process. A scanner is a program that takes a sequence of characters (the source file of the program) and produces a sequence of tokens that will be used to feed the compiler’s parser, the next phase of the compilation process. So, for example, the input A := B + 4 Would translate into the following tokens: IDENTIFIER (Value = “A”) OPERATOR (Value = “:=”) IDENTIFIER (Value = “B”) OPERATOR (Value = “+”) INTLITERAL (Value = “4”) The way that we define tokens in a programming language is with regular expressions. For example, a regular expression that defines an integer literal token looks like: [0-9]+ (read: “1 or more digits”), while a regular expression that defines a float literal token looks like: [0-9]+˙[0-9]* | ˙[0-9]+ (read: “Either 1 or more digits followed by a decimal followed by 0 or more digits; or a decimal followed by 1 or more digits”) While you can write a scanner by hand, it is very tedious. Instead, we typically use tools to help us automatically generate scanners. The tools we recommend you to use are either flex (if you’re planning on writing your compiler in C or C++) or ANTLR (if you’re planning on writing your compiler in Java). flex is available on most Unixes/Linux (including the ecegrid machines), while ANTLR requires a download. If you want to use other tools to generate your scanner, feel free, but we will be able to provide less help. 3.1 Token definitions We will be building a compiler for a simple language called MICRO in this class. The token definitions (written in plain English) are as follows: an IDENTIFIER token will begin with a letter , and be followed by any number of letters and numbers . IDENTIFIERS are case sensitive . INTLITERAL: integer number ex) 0 , 123 , 678 FLOATLITERAL: floating point number available in two different format yyyy . xxxxxx or . xxxxxxx ex) 3.141592 , .1414 , .0001 , 456.98 STRINGLITERAL: any sequence of characters except ’” ’ between ’” ’ and ’” ’ ex) “Hello world ! ” , “∗∗∗∗∗∗∗∗∗∗∗” , ” this is a string ” COMMENT: Starts with “//” ( without quotes ) and lasts t i l l the end of the line e . g . // this is a comment e . g . // any thing after the “//” is ignored Keywords : PROGRAM,BEGIN,END,FUNCTION,READ,WRITE, IF ,ELSE,ENDIF,WHILE,ENDWHILE, BREAK, CONTINUE, RETURN,INT,VOID,STRING,FLOAT Operators := + − ∗ / = != < > ( ) ; , = 3.2 What you need to do You should build a scanner that will take an input file and output a list of all the tokens in the program. For each token, you should output the token type (e.g., OPERATOR) and its value (e.g., +). You are provided a set of sample inputs and outputs as part of the starter files of the repository. These are the only inputs we will test your compiler on. Your outputs need to match our outputs exactly (we will be comparing them using diff, though we will ignore whitespace). 3.3 Hints Note that even though our sample outputs combine together a bunch of different tokens as a single type (e.g., all keywords have the token type KEYWORD), you will be better served by defining every keyword and operator as a different token type (so your scanner will have different tokens for, say, := and git tag -a -m “” This will attach a tag with name to your latest commit. Once you have a version of your program that you want to submit, run the following commands: > git tag −a cs316pa1submission −m “Submission for PA1” > git push −−tags We would be using a tag name cs316pa1submission. So, the above commands will create a tag named “cs316pa1submission” and push it to the remote server. The grading system will check out whichever version you have tagged “cs316pa1submission” and grade that. If you want to update your submission (and tell the grading system to ignore any previous submissions) type: > git tag −a −f cs316pa1submission −m “Submission for PA0” > git push −f −−tags > git tag -a -f cs316pa1submission -m “Submitting PA1” overwrites the tag on the local repository. git push -f –tags, pushes the updates and overwrites the tag on the remote repository (on Github). These commands will overwrite any other tag named cs316pa1submission with one for the current commit. Please be careful about the following rules: 1. For each assignment, you should tag only one version with cs316pa1submission. It is your responsibility to tag the correct one. You CANNOT request regrading if the grading program retrieves the version that you do not want to submit. 2. After tagging a version cs316pa1submission, any modifications you make to your program WILL NOT BE GRADED (unless you update the tag, as described above). Do not send your code for grading. The only acceptable way for grading is to tag your repository.
In this project your will implement a data structure that models a bag with items. Each item has a short description, a weight (in pounds), and a price (in US$). A bag weighs the total weight of the items it carries. A bag also has a weight limit. Therefore, it does not allow items to be added if the weight limit cannot be preserved. As you will see, our implementation of a bag is going to be very similar to the linked list data structure discussed in class. The Item Class Finish the two constructors of the Item class. The generic constructor takes 3 parameters: description, weight, and price. The weight of an item cannot be less than .05 lbs (value defined by the MIN_WEIGHT class variable). Also, the price of an item cannot be less than US$ 1 (value defined by the MIN_PRICE class variable). The other constructor only takes the item’s description, setting its weight and price to .05 and 1, respectively. Two items are equal if they have the same description, disregarding their weights and prices. The comparison is done without taking case into consideration. Therefore, items with descriptions like “laptop” and “Laptop” are considered to be equal. The provided compareTo method allows items to be compared by price. For example, to check if item referenced by variable “a” is cheaper than item referenced by variable “b” you would do: if (a.compareTo(b) < 0) System.out.println(a + ” is cheaper than ” + b); The Bag Class A bag can be created by setting its weight limit. If the weight limit is not informed, it is assumed to be 50 lbs (value defined by the DEFAULT_WEIGHT_LIMIT class variable). As said in the introduction section, a bag is modeled as a linked list. Because you can only add Item objects to the bag, the head of this specialized linked list is a reference to a Node. To avoid the cost of having to traverse the whole list to compute the bag’s weight, a variable with the same name is maintained, and it should always reflect on the bag’s current weight. Therefore, whenever a new item is added to the bag, the new item’s weight must be added to the bag’s weight variable; also, whenever an item is removed from the bag, the removed item’s weight must be subtracted to the bag’s weight variable. Other than the constructors, you are expected to implement the following methods in the Bag class: boolean isTrue() double weight() double weightLimit() boolean add(final Item item) int count() int count(final Item item) int price() Item mostPricey() boolean contains(final Item item) boolean remove(final Item item) boolean removeAll(final Item item) Each method is described by a TO-DO embedded in the provided code. The BagDriver ClassThis was a famous screensaver that was in 99% of the Windows computers in the 90s. Before YouTube, we spent hours just looking at this screensaver wondering what the character, named Johnny Castaway, would do next. Imagine that you, like Johnny, will have to spend an indefinite amount of time on a desert island. To survive on this inhospitable island, you are only allowed to carry a 30 lbs bag. Which items would you bring with you? Using your Bag class, create a bag with items that you would bring with you. Display your bag (with proud), show whether your bag contains a “firecracker” or “firework” items, and what is the most pricey item in your bag. The BagTest Class To help you check whether your Bag class implementation is correct, a few tests were provided. Submission To avoid having points deducted, you MUST submit your project using the right format, which is: a zip file named “prg_01.zip” with the following files ONLY: Item.java Bag.java BagDriver.java Those files should NOT be in a subfolder. This is the structure that I am expecting: prg_01.zip |___Item.java |___Bag.java |___BagDriver.java Make sure to write your name in all source files submitted. Use the provided comment sections. Rubric +10 Item class (+5 for each constructor) +65 Bag class +5 constructors +2 boolean isTrue() +2 double weight() +2 double weightLimit() +7 boolean add(final Item item) +5 int count() +5 int count(final Item item) +5 int price() +7 Item mostPricey() +5 boolean contains(final Item item) +12 boolean remove(final Item item) +13 boolean removeAll(final Item item) +25 BagDriver class +5 Bag instantiation +7 items addition +3 bag display +5 if statement checking if bag contains items +5 display of the most pricey item -5 file submitted does not follow the format asked -5 comment sections of the source files do not list the name(s) of the student(s)
