Category: Programming Language

Robot Arm Control

Posted on | by andrewlai61616

It’s easy for us to point at a certain coordinate in space. That’s mainly because we simply locate the point with our eyes, and continuously check if our finger is pointing at that very spot. It surely will be more difficult without using eyes, and this is the case for robot arm control with no image feedback.

Think of a two arm robot (Fig. 1). We usually want to reach a certain point on the x-y plane. The problem is only the angle of the joints can be controlled. How can we correlate the joint angles of a robot with its tip coordinate? Things get harder when it comes to 3D space, and even harder considering its rotation.

In this project, I created a program that can calculate the every joint angle of the 6-arm robot IRB140 for positioning it at a given (x, y, z) coordinate and rotation.

Figure 1. Dimensions of the IRB140 robot (unit: mm) [1].

The problem for reversing an operation from the specified coordinate and rotation to every rotation angle of an arm joint lies in the field of inverse manipulator kinematics. There may be multiple solutions that lead to the same result. Thus, I implemented the Pieper’s solution [2] for solving the joint angles for the IRB140 robot.

Here’s a video demonstration for precision control of the IRB140 by only giving the joint angles as the input. The robot follows a trail surrounding a paper box with the tip of the last arm always pointing at the center of the box.

[Source code for robot arm control program]

1. ABB, IRB140 product specification, 2019, https://library.e.abb.com/public/2893a5756d204e19aba0d37c2a2cadc6/3HAC041346%20PS%20IRB%20140-en.pdf
2. Craig, J.J., Introduction to Robotics: Mechanics & Control. 1986: Addison-Wesley Publishing Company.

Guess the Number (iOS)

Posted on | by andrewlai61616

This is the first iOS game I had made using Xamarin, and is the second project of the guess the number series (after Guess the Number (Windows) and prior to Guess the Number AI). (The two-player game is also named Bulls and Cows.)

At the start of the game, a random 4-digit code is generated by the app and the player starts to guess that code. The player can restart the game anytime by pressing RESET, and a history of guesses and results are shown in a list at the bottom.

Here’s a demonstration of the app:

Considerations for app development are quite different from computer programs, such as the different screen sizes for different mobile platforms, and most of the time only a touch screen can be used. After finishing this project, I acquired some important fundamental concepts and know-hows for app design.

Guess the Number AI

Posted on | by andrewlai61616

After completing the first two projects of the Guess the Number series (Guess the Number (Windows) and Guess the Number (iOS)), I made an AI that can play this game at a high-human level.

It has been proven that at most 7 turns are needed to guess the answer, with a best average game length of 5.21 turns. For this game, all the possible combinations (e.g. “0123”, “7381” …) can be saved into a 1D array. After each guess, the possible combinations for the answer will be reduced. Therefore, the algorithm of the program is written for finding a number that will minimize the maximum possible combinations left. The time complexity for each turn is O(n3), and an average of 5 turns of guessing if needed for an arbitrarily chosen number.

For using the program, the user must first choose a 4-digit answer (e.g. “0123”), and input the two numbers [A] and [B] according to the game rules and the numbers guessed by the program. For instance, if the answer is “1357”, and the AI guesses “3127”, the user must input 1 2 ([A] = 1, [B] = 2).

Here’s a demonstration of the AI program guessing the answer “8192” in 5 guesses:

[Download Guess the Number AI program]

[Source code for the Guess the Number AI program]

Nonogram AI

Posted on | by andrewlai61616

Nonograms (also known as Picross, Griddlers, Pic-a-Pix, and various other names) are picture logic puzzles, in which the cells in the grid must be colored or left blank according to the numbers on the side of the grid to display hidden pictures.

Figure 1. The initial and complete state of a 25×25 grid Nonogram.
(Source: https://www.nonograms.org/nonograms/i/32344 )

For a classical type of game, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of “1 2 3” would mean there are sets of one, two, and three filled squares, in that order, with at least one blank square between successive sets.

Solving Nonograms can be very time-consuming, and can be tremendously brain-twisting as the grid size increases, thus I created an AI program for automatically solving these puzzles.

The program utilizes the depth-first search algorithm that runs recursively from the top to bottom row. For the jth column of the ith row, the black or blank spaces must satisfy the tomographic rules formed by the numbers of the current row and column. This is a relatively simple approach for calculating the answer. However, because the algorithm does not solve the game using a more intuitive method for solving interrelated constraints, it will use a lot of time for big grids (over 40×40).

For the input format of this program, two numbers indicating the number of rows and columns are given first (n and m). Afterwards, there are n rows of data, with each row k starting with a number nk indicating how many numbers are given in that row, and followed by nk numbers representing the discrete tomography of black spaces of that very row; then there are m rows of data, and also starting with a number mk for the kth row, and followed by mk numbers representing the discrete tomography of black spaces for the kth column.

Here’s an example input for the Nonogram in Fig. 1:

25 25
1 8
2 7 3
1 16
2 11 4
2 13 2
2 14 2
1 18
2 8 4
2 6 4
2 5 5
3 4 2 2
3 4 3 1
3 3 2 1
2 3 2
2 3 2
3 2 1 4
3 2 1 4
3 2 1 4
3 3 1 4
2 5 4
1 11
1 10
1 5
1 5
1 6
1 1
1 2
1 2
1 4
1 11
1 13
1 15
2 9 3
2 8 3
3 7 5 2
3 7 3 4
3 6 2 3
3 8 3 2
2 13 2
2 10 2
3 5 5 3
4 4 1 4 6
4 1 2 2 8
3 3 1 10
4 3 1 4 4
4 2 1 2 3
3 2 1 2
2 2 1
2 2 1
1 1

A demonstration for using the AI program for solving a 39×50 Nonogram in about 22 seconds is shown below. The result displays an owl sitting on a branch (Fig. 2).

Figure 2. The complete state of a 39×50 Nonogram displaying an owl on a branch.

[Download program for the Nonogram solver AI]

[Source code for the Nonogram solver AI]

Othello AI

Posted on | by andrewlai61616

Othello (a variant of the traditional game Reversi) is a two-player strategy board game played on an 8×8 square field, where each player takes turns placing black or white pieces and capturing the other player’s pieces.

Figure 1. Othello board game.

The Othello AI program is the second board game AI that I have written in junior high school (the first is the Tic-Tac-Toe AI). Just like the programming strategy for the tic-tac-toe AI, I used the logic thinking experiences that I had learned while playing this game, and hard-coded some summarized strategies into this program.

Compared with the tic-tac-toe AI, which has a game-tree complexity of 9! = 362880, Othello is much more complex, yielding a stunning complexity of approximately 1058. This makes the game still mathematically unsolved up to this very day. Therefore, instead of calculating the definite winning strategy, this Othello AI rather tries to find relative advantageous points (e.g. the corners), and moves that will temporarily maximize the number of pieces which it occupies by the coded algorithm, making it a beginner ~ intermediate level AI.

Here is a demonstration of using the Othello AI program:

[Download Othello AI program]

[Source code for the Othello AI program (Visual Basic 6.0 form file)]

Sudoku AI

Posted on | by andrewlai61616

Sudoku is a commonly known logic puzzle game, and had been one of my favorite puzzle games.

Having the experience for creating the simple Tic-Tac-Toe AI, I started to take on this challenge for creating an AI that can solve Sudoku.

Figure 1. The initial and complete board state of an expert-level Sudoku game.

I had written this AI program when I was in junior high school using Visual Basic 6.0. Having no prior knowledge for algorithms and data structures (which I learned in senior high school), I came up with a rough version of the backtracking algorithm myself, and implemented it on the AI. Here, the backtracking algorithm is a kind of depth-first search (DFS), and is guaranteed for finding a valid solution. Constraint programming is also integrated with the backtracking algorithm, since it is a very intuitive way for solving the puzzle.

Here is a clip demonstrating the Sudoku Solver program solving a hard-level Sudoku in around 5 seconds:

Here is another one that solved an expert-level Sudoku in around 44 seconds:

[Download program for the Sudoku Solver]

[Source code for the Sudoku Solver (Visual Basic 6.0 form file)]

Gomoku AI

Posted on | by andrewlai61616

Although entering a department different from Computer Science (CS), I still had a majority of acquainted people in NTU-CS. One day, a friend of mine who was studying in CS challenged me of making an AI of some board game. The two of us would make AIs of that game and try to win the other one using the AI. Thinking it might be some challenging but interesting subject, I started to make this Gomoku AI.

Figure 1. Game playing demonstration of the Gomoku AI program.

Being a board game with so many possible states (more than the Othello AI I had made when I was in junior high school, which only has a 8×8 grid) , it is considered overly time wasting for the AI to traverse all the possible combinations, even just within 10 moves! Game tree graphs, graph traversal algorithms (e.g. DFS, BFS) and optimal searching algorithms (e.g. Alpha–beta pruning, A*) are usually implemented for decreasing computational time and achieving the best strategy. In this project, I only used the depth-first search (DFS) algorithm, along with some hard coded optimization decisions to create this program. Although being able to place a few initial pieces successfully, the program suffers from a large amount of computational time being spent. Most of the time after a few moves, the program will just run for a few hours (or days) before taking the next move, which is obviously very a serious problem for the AI.

Nevertheless, the environment and rules of the Gomoku game engine was successfully constructed, which allowed two players to play against each other. Nowadays, these board game AI are usually designed using deep neural networks, such as AlphaGomoku, an Alpha-Go-based Gomoku AI. Constructing these AIs would be a possible future work for optimizing this game agent.

Tic-Tac-Toe AI

Posted on | by andrewlai61616

Artificial intelligence (AI) has long inspired me, and had spurred me on to come up with interesting programs or projects that I had not imagined before. Since great oaks from little acorns grow, this tic-tac-toe AI project is the first and one of the most important programs I have made that can be said to possess artificial intelligence. (~age 15, 2011)

Either with the player playing first or the computer, the AI will never lose! Being a very simple game that one could easily master, tic-tac-toe can yet be quite complex in a way in that there is actually a total of 255168 possible outcomes! Fig. 1 illustrates all the possible board states until the 5th move using an optimal strategy with the 1st move at the center (States that can arise from mirroring or rotating the shown states are excluded). The green circled states are those which the circles have won, and the yellow ones are those which the circles will eventually win while continuing to implement the optimal strategy. We can see that it actually gets quite complicated after the 3rd move.

Figure 1. Possible states of Tic-Tac-Toe until the 5th move starting from the center.

Since back then I knew nothing about algorithms (which I had started to learn at senior high school), I hard coded almost all the conditions using very basic syntax: If…Else…End If and For…Loop. The AI will sometimes move randomly, but it will always follow an optimized strategy. It took me ~650 lines of code and several days of hard work to complete.

This project demonstrated the possibility of programs to achieve human level performance for playing simple games. Although objectively not considered an astonishing one, I was surely amazed and unprecedentedly inspired by the potential of programming algorithms for AI; which further on motivated me to create AI programs of increasing difficulties (refer to Gomoku AI, Sudoku AI, Othello AI, Nonogram AI, Guess the Number AI, Minesweeper AI).

Heat Transfer Dynamic Plotting

Posted on | by andrewlai61616

It may often be increasingly hard to comprehend dynamic properties using only static figures shown on a textbook. There is more need for data visualization for better understanding the complicated world around us…

This is a demo program that I have written in a course of heat transfer. I served as the teaching assistant and assisted my professor for delivering the curriculum. In order to let the students understand some time-dependent properties between the temperature and position of a heat transferring process, I used Python and the library Matplotlib for customized visualization of the heat transfer process.

Compared with a static plot of the same process (Fig. 1), this dynamic plot (Fig. 2) intuitively demonstrated the nature of temperature change according to time.

Figure 1. Static plot of normalized temperature (1-Φ) vs normalized position (η) at different normalized time (τ) using OriginLab.

Figure 2. Dynamic plot of heat transfer.