Fun With Racket: MIRTO Bots

MIRTO Bots

What is MIRTO?

---

MIRTO (the MIddlesex  Robotic plaTfOrm, also known as Myrtle) is an Arduino+Raspberry Pi platform currently used for teaching in the first year of the Computer Science degree at Middlesex University. It is developed as an open-source platform and the design and source code are available online.

MIRTO bot at Middlesex

A base layer incorporates Infra-Red sensors, bump sensors and a pair of HUB-ee wheels.In the center, an Arduino Uno collects the data from the sensors and is connected to the wheels to drive them. The top layer for Computer Science students is a Raspberry Pi that is connected to the Arduino Uno board by means on a serial connection on the GPIO pins.

Computer Science students will work mainly at the Raspberry Pi level, possibly extending the core platform with additional features (USB cameras, a fourth layer on top, etc.). More importantly, the platform offers a number of opportunities for teaching core Computer Science notions: from product of finite state machines to concurrency and synchronisation when reading the encoders, from networking at all levels (IP, TCP, applications) to data structures, functional programming, etc.

Projects and Code

---

Although I didn't track all projects, the MIRTO did make quite a few appearances in my first year of university.

Project I: Follow The Path

We started off planning, as a group, how we would approach testing the robot.  We initially went with the worksheet as a guide and start-up for the direction to go.  

Initially, we wanted to see if it would move, so we recreated the program we saw on the scratch worksheet and tried to see if the robot would react, which it did, once we connected to it. We also made the Hello World text show up on our LCD screens. 

We started off with a basic ‘U’ track on the table, with a piece of tape. Our code explains that “If the mid sensor (1) is greater than 500 (used as a constant value, chosen by trying to keep the robot on the tape), then the robot should move forward, else it should stop.”

Follow the part - U track

Working on MIRTO with Scratch

An issue that we encountered is that the robot increased in speed when it got to the turning point and then fell off the table. We initially assumed that the issue was the sensors, however we found out that using 200/100 was too fast and so the robot would drop from the table. We then changed it to 100/50 which meant the robot would drift across the table without falling down.

Final code

We finally came to this conclusion through trials with different functions and variables. We did try it out, but we were not so successful in making it work. Initially, it did work and we added on parts for it, and it did diverge from the track a bit.

Project II: MIRTO Orchestra

Sequence diagrams: connecting to MIRTO bots

First phase included selecting the music and then converting musical notes into its corresponding frequency in Hz.

We had to use ASIP (library created by MDX) function called playTone which has a signature of playTone : (Hz , ms) -> (sound). We also had to convert the time of musical notes into milliseconds.

Facing a problem of synchronization, we tried multiple ways of running the files of the different voices; we tried the Putty version on which we would try to run both at the same time. 

Then we found Putty Connection Manager which made that task easy for us. Even after that we still had synchronization problems. Eventually, we realized we would have to connect the robots to a network. We have done that by creating a file with a TCP listener which connected to an IP and would receive an Input and then reply with the Output. The input: Frequency in Hz and the Time in Milliseconds.

And now we had to create a conductor to send the instructions to the multiple robots.

We created a function that would send those values and by some miracle, it all worked.

Having the problem of synchronization solved we only had to put together all the functions containing the music in the conductor file.

Finally, we created a video demonstrating our work and also a Website on which you can play the music and also read step-by-step our work.

Read More

Fun With Racket: Morse Code

Racket Morse Code

Learning to code with Racket, BSc Computer Science, 2016.   You can find the project by clicking the Github icon. ->

Introduction

---

When learning to code, it's always practice... practice... and more practice. Even if it has nothing to do with career development or a project assignment, or simply useful, practice is the most important thing.

To play around with data types in Racket, particularly lists and structs, I set myself a project working with Morse code (because why not), mostly because I could use it on multiple fronts. Text-based output, GUI display, and simple output with the Arduino.

Racket Environment

---

Racket is a programming language - a dialect of Lisp and a descendant of Scheme. It allows functional programming and other different models and ideas that programmers aren't even aware of. It's not the most infamous when it comes to languages, but it is a great starter and easy-to-build concepts and training.

The environment, Dr. Racket, is quite intuitive and once you get to know it a little better, it can become incredibly easy to understand. It usually works in a read-eval-print loop, or REPL. Imagine your machine just sitting there and waiting for something to read. Once it gets it, it evaluates and then prints the result.

Dr. Racket Environment

Implementation

---

As mentioned in the Introduction, there were three parts to this so-called "practice" project.

Part I: Text-based (console) output

Experimenting with different data types (sets, arrays, structs, lists), I found out that the best structure for this project is lists - more specifically, nested lists. Using lists to build a dictionary of alphabets and the morse code equivalent, using basic conditionals and loops, I set up the function to translate strings to morse code.

Dictionary of alphabets (nested lists structure)

Console code run

Part II: GUI

With the basics all completed, I further implemented a GUI-based application after covering the lessons during university classes. I added a little Disney magic to it because I practically live and breathe Disney.

Using black and red square images, and some blink code to change the images to blink 1 second and 2 seconds for dots and dashes respectively,  I managed to "animate" a sequence based on user input.

Racket GUI: Black square blinks

Part III: Arduino

Finally, I wanted to test my hardware knowledge. I'm not the biggest fan of dealing with hardware but might as well make it something that I was interested in. It didn't take much coding to get the setup done as I already had the base functions down.

After connecting to the GUI, based on user input, the bulb (connected to Arduino) would blink to match the GUI.

Evaluation

---

Final video project: GlobAR

Read More

Java: Travelling Salesman Problem

Travelling Salesman Problem

Artificial Intelligence module, Computer Science 2018.   You can find the code by clicking the Github icon. ->

Overview

---

Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible path that visits every city only once and returns to the origin. The problem is a famous NP hard problem. There is no polynomial time known solution for this problem.

The project aims to build a system in Java that solves travelling salesman problems. The travelling salesman problem is to go to each city exactly once and return to the start. Solving the problem should give a path and the length of the path. There are optimal solutions, that is solutions with the shortest path.

Algorithms Used

---

Depth First Search

The DFS is the most fundamental search algorithm used to explore nodes and edges of a graph. It runs with a time complexity of O(V+E) and is often used as a building blocks in other algorithms. A Depth First Search plunges depth first into a graph without regard for which edge it takes next until it cannot go any further, at which point, it backtracks and continues.

For the coursework, the use of the DFS is basic. It prints out a single path starting from a starting city. It doesn’t necessarily take the optimal path, but it goes through all the cities and returns to the origin.

Dijkstra’s Algorithm

Dijkstra’s algorithm is a Single Source Shortest Path algorithm for graphs with non-negative edge weights. You maintain a distance array, with length n (n = number of nodes) and the distance to every node is initiated as infinite. 

A separate array, parent, is created. Value of parent[n] for a specific node, n, stores parent node of n in shortest path tree. Parent of origin node is -1. Whenever we find shorter path through a node, we make it the parent of current node. This, joined with the nearest neighbor technique, is used as a partially effective way of finding the shortest path. It does get close, but it isn’t always right.

Brute Force

The Brute Force technique consists of methodically computing all possible candidates for the solution and checking the cost of each possible tour, returning to the origin. It does achieve the optimum path, but it is very computationally expensive. This runs with a time complexity of O(n!), where n is the number of nodes in the graph.

Dynamic Approach

The Dynamic Programming solution to the TSP significantly improves the Brute Force technique, taking it from O(n!) to O(n^2*2^n). The main idea is to compute the optimal solution for all the sub paths of length n (n = number of nodes), while using information from the already known optimal partial tours of length n-1.

To compute this, we need to store two things from each case: Set of visited nodes in the sub path, Index of last visited node in the path. The best way to represent the set of visited nodes is to use a single 32-bit integer (as stored in the cache table).

Training Data

---

The training data provided were four files with a fairly small amount of data. Having looked at the results, the Dynamic Approach would seem to be the likely optimal way to search the space.

Test Data

---

The test data provided were four text files. The Dynamic Approach did prove to work consistently in this space, given a larger amount of data. However, after forty points, it did seem to give a little trouble.

Conclusion

---

While there are numerous solutions and algorithms to work through this problem, there is no one right answer and all depends on the search space and depth. The Traveling Salesman Problem (TSP) is believed to be an intractable problem and have no practically efficient algorithm to solve it. 

References

---

Baeldung. (2018). The Traveling Salesman Problem in Java | Baeldung. [online] Available at: https://www.baeldung.com/java-simulated-annealing-for-traveling-salesman [Accessed 10 Dec. 2018].

Bari, A. (2018). 4.7 Traveling Salesperson Problem - Dynamic Programming. [online] YouTube. Available at: https://www.youtube.com/watch?v=XaXsJJh-Q5Y [Accessed 11 Nov. 2018].

Fiset, W. (2018). Graph Theory Playlist - YouTube. [online] YouTube. Available at: https://www.youtube.com/playlist?list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P [Accessed 12 Oct. 2018].

GeeksforGeeks. (2018). Printing Paths in Dijkstra's Shortest Path Algorithm - GeeksforGeeks. [online] Available at: https://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/ [Accessed 9 Dec. 2018].

GeeksforGeeks. (2018). Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming) - GeeksforGeeks. [online] Available at: https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ [Accessed 9 Dec. 2018].

Google+, f. (2018). Applying a genetic algorithm to the traveling salesman problem. [online] Theprojectspot.com. Available at: http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 [Accessed 03 Dec. 2018].

Programming-algorithms.net. (2018). Travelling salesman problem. [online] Available at: http://www.programming-algorithms.net/article/48915/Travelling-salesman [Accessed 9 Dec. 2018].

Saurel, S. (2018). Calculate shortest paths in Java by implementing Dijkstra’s Algorithm – All for Android, Android for All. [online] Ssaurel.com. Available at: https://www.ssaurel.com/blog/calculate-shortest-paths-in-java-by-implementing-dijkstras-algorithm/ [Accessed 9 Dec. 2018].

Read More

Unity Project: Location Based PacMan

Location Based PacMan

This project was done as a part of the Creative Technology course dissertation, 2021.   You can find the Unity project by clicking the Github icon. ->

Introduction

---

This was done as part of the GlobAR project (click here to read more), but still deserved to stand on it's own. Out of pure boredom and nostalgia, I was playing PacMan one evening, while getting my mind away from a bug on a project I was working on.

Somewhere in that frustration, I thought up a Location-based version. Imagine actually being chased by a PacMan ghost, running around getting points and power-ups. I found it funny - funny enough to try creating it. It has the potential to be a great work out app, or just a fun game to play.

NavMesh and Unity

---

NavMesh, short for Navigation Mesh, is a Unity package that helps create walkable surfaces in a Unity game, allowing players to calculate walkable routes, between two locations in the game world. Documentation on this was limited as it was mostly for static planes and/or 2D game environments.

When getting it to dynamically generate with the map on Play, the building meshes, and materials seemed to fade and turned into a light blue tint that would occasionally flash. Using a NavMeshAgent, I was able to create a quick enemy to catch the user’s character (simulating PacMan). Accessing the app on a phone created too much lag to continue with the project. Exploring a different method might have been a better way to go.

Development

---

Moving away from AR based applications, I thought I would focus on the geolocation. The idea of real world PacMan seemed almost impossible to pass up as I thought about it. Not only would it be interesting, but it would also make for a good run. Of course, during these times, it may not be so accessible due to lockdowns and staying indoors. 

Making the map walkable was not very wise in this case, as the NavMesh component (explained in Section 6.2.2) I had used was not very compatible with the application. The use of the NavMesh component was to enable to enemy character to follow the player to real world positions.

Evaluation

---

Final video project: GlobAR

During such a chaotic time, with COVID-19 and the lockdowns, working with locative technologies and testing it proved to be limited. Even when it came to being at home and working, I made the most of what I could. There are a lot of techniques looked at throughout this project.

Read More