Author: stelanof

This week, I optimized the simulated shot algorithm and worked on our final presentation slides. For the simulated shot algorithm, I added more concrete vectorization for pocket detection and wall collisions. Additionally, I optimized ball collision checks by using scipy.spatial.cKDTree, which is an optimized form of the spatial hashing class I implemented earlier. Now, instead of using vectorized numpy checks with spatial hashing, which was in O(n), we use the cKDTree (a binary tree representing different locations on the board) to find nearest balls in O(log n). Additionally, SciPy uses underlying C code for the cKDTree implementation, which further optimizes the runtime. With these fixes, I was able to improve the shot simulation runtime by almost 600%.

Before OptimizationsAfter Optimizations

I will be spending this next week working on the final presentation, final report, and getting everything ready for the final demo. I am still on schedule.

This week, our group’s primary focuses were on the interim demo and continuing to develop/optimize our project as we get closer to the end of the semester.

Overall, the interim demo went well, we were able to successfully take a picture of the current state of the table, detect the pocket locations, detect and classify ball locations, run our best shot algorithm, and then display the best shot onto the board for the user to see. Below is a photo of what that display looks like, and here is an example of what that looks like in action.

A couple of things that we need to work on after the interim demo are

1. During the demo, we would manually send data between subsystems, ie Luke would take the picture of the board and send it to Kevin, who would run the CV algorithm on it and then send that data to Sammy to run best_shot and project the shot. We are currently working on a main file to run all of this on one computer for the final demo
2. Ball categorization is good, but still needs some work. Kevin is currently working on refining the color thresholding for ball categorization, as similarly colored balls are still being categorized as the same (2-ball and 4-ball).
3. Simulated annealing is still random, so sometimes the best shot algorithm returns a local minimum instead of the global minimum. Sammy is working on optimizing the shot simulation so that the best_shot’s simulated annealing algorithm can run with more iterations.
4. The camera is set to auto-focus, so we would sometimes need to refocus the camera before starting the whole process. Luke is looking into testing different configurations to achieve a more stable image feed that is always in focus.
5. Projector/Camera placement is good, but can be better. Luke is looking into the optimal placements for the projector and camera so that they most closely align with the real-world pool table.

Alongside these development/optimizations, we are working on a couple of post-MVP additions to our project. Luke is looking into creating a file that monitors ball movement through the camera so that it automatically starts the whole process when the balls stop moving, instead of requiring the user to click a button. Additionally, the team is discussing whether or not to use a Raspberry Pi to host a web server with a database of a users previous games so that they can see how much they’ve improved.

Overall, there is no change to our schedule — we are essentially at MVP. Everyone is on track for their tasks, and we believe we will have a good working final project by the time final demos happen.

This week, I worked on optimizing the physics simulation to improve a simulated shot’s runtime. During the interim demos last week, we noticed that the best shot algorithm would sometimes give a local minimum instead of a global minimum. I touched on this a bit last status report, but this is happening because simulated annealing is inherently random, and the fewer iterations it goes through results in more random outputs. To fix this, I tried implementing the physics simulation in C++, then using pybind11 to call the C++ simulation in the best shot algorithm file (which is in Python). Unfortunately, due to the overhead created by having to convert data from Python types to C++ types, the latency didn’t improve at all — the runtime was much slower because of the computational overhead.

I then tested three different variations to see which had the best runtime: 1) purely Python, 2) Python best shot & C++ shot simulation, and 3) purely C++. I figured that since C++ is an inherently quicker language than Python, option 3 would have the best runtime. However, through testing, I still found that option 1 (purely Python implementation) had the best runtime. I believe this is because Numpy vectorization in Python is incredibly optimized, and the C++ version of Numpy (Xtensor) is not. Below are the average runtimes of the shot algorithm for the three implementations on 10,000 random board positions (note that my computer was not plugged in, so runtime is slightly slower than the 25ms we were getting earlier with option 1).

Purely PythonPython & C++Purely C++

This next week I will look into different ways to optimize the runtime of the purely Python implementation. I am still on schedule and everything I am working on as of now is pretty much post-MVP.

This week, I finished the find_best_shot algorithm and created a variation of the display mapping algorithm that creates the image of the shot we will project on the board.

For the find_best_shot algorithm, I switched the implementation from a brute force approach to a much quicker simulated annealing approach. This approach calculates the initial angle between the cue ball and the target ball (the lowest numbered ball on the board). This angle is either the direct angle between the cue ball and target ball, or the angle that bounces the cue ball off a wall into the target ball. The algorithm then adds a random amount of angle, power, and spin to the previous shot and then simulates it. If this selected shot improves the solution, it is always accepted. Otherwise, the algorithm makes the move anyway with some probability less than one, which exponentially decreases based on the “badness” of the move.

To fit within the use-case requirements, I constrain the algorithm to return the best angle, power, and spin within either 1000 iterations or 4 seconds. This is then passed into the display mapping algorithm to show what the outcome of the shot will be. These images are attached below.

However, as you can see, since the simulated annealing algorithm is essentially random, the 4-second constraint can sometimes lead to different shots depending on what “direction” it takes in hill-climbing. This means that it will sometimes return a local minimum instead of the global minimum shot. For example, in the attached images, the best shot algorithm sometimes returns the shot that just pots the 1-ball (second image), a local minimum, instead of the shot that pots the 9-ball (first image), which is a global minimum since it wins you the game.

To fix this, I have begun to create a C++ implementation of the physics simulation to speed up the simulation time from an average of 25ms to hopefully under 10ms. I will not be finished with this implementation in time for the interim demos, but I hope to be finished with this by the time final demos come around.

I am currently on schedule and will be meeting with Kevin and Luke to integrate our three DeepCue subsections in time for the interim demo.

This week I spent my time working on the find_best_shot algorithm for the physics simulation portion of our project. Currently, my approach is good and finds the 9-ball shot that: a) hits the lowest numbered ball on the table, b) does not result in a scratch, c) pots 1+ balls, d) sets up the cue ball to be closest to the lowest numbered ball on the table, and e) occasionally pots the 9 ball if possible.

However, I am still using more of a brute-force approach than a greedy one. I am thinking of ways to use some Simulated Annealing to find the optimal shot we can take. This will require tweaking parameters that determine the “score” of a shot — this includes balls potted, where the cue ball ends up, etc. I will be spending my time this upcoming week implementing my algorithm and optimizing it to complete in under four seconds as specified by our use-case requirements.

I am still on schedule and, again, hope to be done with the best shot algorithm + display mapping before carnival so that we can test MVP.

This week, I spent the majority of my time finishing up the physics simulation. I created the function simulate_shot, which takes the state of the board and a given shot’s angle, power, and spin and then simulates how that shot would play out on an actual pool table. I spent a lot of time researching how to calculate the inelastic collision when different balls collide, and I believe I have a pretty good implementation of it. I also added optimizations to the shot simulation code, including vectorization through NumPy and handling ball collisions with spacial hashing, to get the average runtime of a single shot simulation down to ~25ms from ~75ms.

Additionally, I created a function simulate_shot_with_animation, that draws and simulates the shot onto a Matplotlib graph. This function and file take 5 consecutive shots with random power, angle, and spin and show the state of the board during and after each shot. I used this testing method to get a visual cue of how my simulation is working. I also used the animation to fine-tune the parameters — like friction, power, and collision coefficients — until I found one that was pretty similar to the pool table we ordered. Attached are pictures of what the animation looks like.

I will be spending my time this next week creating our greedy algorithm that chooses the best shot. I am currently on schedule and hope to be 100% done with implementing and testing this algorithm within 1-1.5 weeks so that we are ready to integrate and test MVP before carnival.

As a team, the majority of our time these past two weeks was focused on the design report and beginning to implement our project. We spent significant time on the design report to make sure that we could best convey our idea of our project to the reader. Additionally, we went more in-depth into how our system works and how each part comes together: creating a comprehensive block diagram, function signatures for software subsystems, choosing and ordering the exact hardware parts we will be using, and more. The more in-depth research/development of our project has made it easier for us to actually begin and go through with implementation, as we will have a majority of it detailed in our design report.

As for implementation, we have started implementing the major software subsystems of our project — the CV and the Physics Simulation. The third software subsystem, the display mapping, will be completed after the physics simulation is finished. Unfortunately, we are in a bit of a roadblock in terms of our physical implementation. We’ve received the projector and camera that we will be using for our project, however, we have yet to receive the physical pool table we will be working on. When we asked the ECE mailing room if they had received the pool table package yet from Amazon, they said it was still delayed. We will be checking again tomorrow after we meet with Professor Brumley, and are hoping the pool table will be in ASAP.

Overall, we are making steady progress on our project despite being blocked. There are no changes to the schedule on the software side of our project, however, we will need to speed up the schedule for our physical side of the project due to not being able to work on it just yet.

For the past two weeks, I spent most of my time on coding and the design report. I put a significant amount of time into the design report before break. I spent the most time on the system implementation section of the design report, where I figured out what different subsystems are and how they would interact with each other. This included coming up with the function signatures of all our software (like getBalls or find_best_shot), figuring out how each function should work, and finally figuring out what each function should take in as input and output to best transfer data from subsystem to subsystem. Additionally, I began a little bit of coding on the physics simulation subsystem. I will be focusing the majority of my time this month on making sure the code for that is well put together. I am currently on schedule and hope to be done with coding by the end of this month so that we can integrate everything and be at MVP.

This week, I spent most of my time on the Design Review Presentation slides. Additionally, I started working on my portion of the coding for our project. I set up our GitHub codebase and installed/set up the necessary dependencies for the physics simulation. I have also begun to work on our Design Review Report and will be meeting with Kevin and Luke tomorrow and throughout the week to get that done in time. The majority of my time in the next two weeks will be focused on the report as well as coding the following: simulating shots and finding the best possible shot. I am on track based on our schedule, however, next week I will have less time to work on capstone as I have two exams and a project due. Thankfully, I will have ample time during spring break to focus on our capstone project.

This week I did more research into the physics simulation portion of our project. I’ve found some Github codebases + research papers/videos that should be beneficial to our algorithm. I also went to the UC basement to play pool with Luke so we could have a benchmark of how many shots it takes us to finish a game of 9-ball. We played three games and averaged around 40-50 shots. We will use this benchmark as a comparison and will hopefully see a decrease in shots taken when we use DeepCue as help.

Additionally, I took some time to make a block diagram of our project for our design presentation. We’ve made a pretty significant change to our project in that we have decided to remove the Nvidia Jetson and instead directly connect the camera/lidar to a computer. So I updated our block diagram + Gantt chart to reflect these changes. I am still on schedule and plan on working on the physics simulation this week. I will have to coordinate with Luke as he will now be helping with the physics simulation since we aren’t using the Jetson anymore. Additionally, we will conduct more benchmark testing with the smaller pool table that we just ordered.