Particle Swarm Optimization

Since my last post, I have spent a lot of time learning about biologically inspired optimization techniques.  Some commonly used biological machine learning methods include genetic algorithms and neural networks.  However, I decided to dive a little bit deeper and try out a few newer algorithms.  The two algorithms I have been working with are called Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO).  In this post I will talk about PSO.

Particle Swarm Optimization

This is a representation of Particle Swarm Optimization.  The solution that is found for a particle is swayed by the global best and the individual particle's best solutions.  http://www.sciencepubco.com/index.php/JACST/article/view/84

PSO is a stochastic technique that is based on the way that swarms move towards a goal.  Each particle is a potential solution (or bee in a swarm) and it moves in some direction with a velocity.  The velocity is determined by a combination of the individual particle's best solution, the global swarm's best solution and an inertia weight.  First developed by Kennedy and Eberhart in 1995, each particle is updated with the equations shown below:

http://web.ist.utl.pt/gdgp/VA/pso.htm

The interesting equation above is the velocity update.  Essentially, the new velocity for particle i is the addition of the previous velocity for that particle times the inertia weight (a function of how many iterations we have performed), the randomly weighted difference between the particle and the particle best and the randomly weighted difference between the particle and the global best.  randomly uniform weighting of the differences is a way of introducing unpredictability into the equation so that the system does not get stuck at a local minimum.  The position update just adds the new velocity to the previous position.

The algorithm for performing these actions is fairly straight-forward as well.  The idea is to update each particle and determine if that particle has a better fitness value than it has ever had before, and then determine if it has a better fitness than the swarm's best fitness.  This way, each particle has the equivalent of a unique mind as well as the swarm mind.  Below is the algorithm specifics:

1. A set of N particles are created such that each particle contains random values in the set.
2. It is determined whether each particle is its best case, if it is, particle i's best is this particle.
3. It is determined whether the best particle is the swarms best case, if it is, the swarm best is this particle.
4. Each particle's velocity and position are updated simultaneously with the new particle and swarm bests.
5. If the global best meets the termination condition or the max iterations are reached, stop.  Else, go back to step 2 and repeat.

Using this algorithm, I was able to solve the N-queens problem.  My implementation can be found here, as a new Seeker in the Do-Anything-Machine.  In the N-queens problem, each particle is an array of rows containing a number that corresponds to a column for the position of each queen.  (For an explanation of the N-queens problem, see the previous post).  The fitness function is simply the number of queens that are on the same horizontals, verticals and diagonals of the chess board.  If the fitness of a particle is zero, the solution is correct.

One issue that I have noticed is that it can usually find a local minimum of the system, but does not always find a global minimum.  My solution was to repeat the algorithm multiple times, until the system met the fitness requirement.

Feel free to let me know what you think of my work in the comments.  I am happy to provide links and help to those who are interested.

The Do-Anything-Machine and the Hopfield Neural Network

Machine learning has become a new fascination for me in the past few months.  I have delved into the complicated world of solving problems with neural nets, genetic algorithms and clustering techniques.  Recently, I started work on the Do-Anything-Machine, a project started by Eric Neuman to build an artificial intelligence for solving any type of problem.  This is clearly a huge task, so it has been open-sourced.  To get involved, I have developed this method of solving the N-Queens problem.

The problem states that there are a number of ways to place N number of Queens onto a chess board with NxN squares, such that none of the queens can capture each other.  One way of solving this problem is by using a Hopfield Neural Network configuration.  A Hopfield net is a single-layer network in which all of the neurons are connected.  In our case, each neuron represents a square on the board, so there are N x N neurons.  Each neuron connection is weighted in a way that all of diagonal, horizontal and vertical squares from the initial square are added into that neuron, and the rest are weighted with zero.   The inputs are a random binary array, where each value in the array is an input into one of the neurons.  The output is also a binary array, with each value being an output from one of the neurons. 

This is an example of a Hopfield network with 6 neurons. (http://www.nnwj.de/hopfield-net.html)

The general method has two parts:

- The Internal process

- The External process

The internal process is an asynchronous method of changing the output of each neuron.

1. A random neuron is picked

2. The input potential of the neuron is calculated by summing the values of all of the horizontal, vertical, and diagonal queens from that square

3. This gives a value that is fed through a sigmoid function

4. The resulting output is then fed back as an input

5. The process repeats

The External process is performed after N x N iterations of the internal process.

1. The internal process is performed N x N times so that the inputs have a chance to evenly distribute

2. The energy (or cost function) of the entire board is calculated

3. If after 3 External iterations, the change in energy is zero, then the system has stabilized, and you have reached local minima

4. If it has not stabilized, then repeat the external process

Due to the amount of randomness, the system converges in anywhere from 3-25 external iterations.  The code for the initial implementation is here.  Please check it out and join in on the project!

Autonomous Quadricopter for Forest Fire Detection

I just recently finished my Master's Degree at Rochester Institute of Technology.  My final project was to design a control system for a Quadricopter that would be able to track forest fires as they spread.  All of the code is at https://github.com/Sanderi44/AR-Drone-Fire-Detection.  Here is the description from the paper:

"An autonomous control mechanism for tracking forest fires was designed with the use of an inexpensive, commercially available quadcopter.  The Parrot AR Drone 2.0 was chosen for this project because of its large open source programming community and many on-board sensors, including two cameras.  Image processing was performed on the video stream sent from the drone’s frontal, high definition video camera.  A few different fire detection algorithms were used with to make sense of the video data.  Then, after processing the video, object detection was performed to find the location of the fire.  Finally, the drone was told to move according to the location of the fire."

Below is the final presentation:

Autonomous Quadricopter for Fire Detection Presenation by Gino Idelson

RIT Tigerbug Paper

I haven't written much about the Tigerbug project in a while, but I wanted to share the paper that our team wrote.  Please take a look and give any feedback that you have in the comments below.  I am very interested in what people have to say about the project!

A Dynamic Control Scheme with Differential Foot Placement for a Hexapod Robot

Learning to Learn

I have always loved learning.  Sure, I haven't always made that point obvious, but in fact, it is true.  So as I depart the world of education for the excitement of the "real world", I can't help but reminisce about my glorious college days at Penn State and RIT.  But now, I am moving on; entering the unknown with nothing but the knowledge and skills I have acquired in 17 years of schooling.  From what I have heard from friends and read on the internet, I am as unprepared today as I was on the day I began school all those years ago.  But I disagree.  I have completed so many projects, homeworks and exams, spent countless hours researching, studying and taking notes. It has to count for something.  But what?  What do they count for?  I think the answer is that they have taught me how to work hard.  Sure everyone "works hard" once or twice in their life.  But at school, especially in my year at RIT, I have pushed myself to places I never thought I could go, almost daily.  I think my real education was in how to focus and complete a task to perfection.  At the end of the day, I am very proud of the work I have done.

The Sentience Stack

A good friend of mine, Eric Neuman, has proposed a roadmap to a living, motivated, creative, sentient being built entirely with Artificial Intelligence and computers.  The best part about the project is that it is open source (meaning github)!  The project is just beginning, but really seems to have legs.  Here is a more apt description of the project:

via simpleactually:

Artificial intelligence sounds awesome, doesn’t it? Machines that can solve problems on their own or answer questions for us would represent an enormous leap forward for all of mankind. The problem is, artificial intelligence as it exists today is not very flexible. Today, AIs are trading stocks, beating you at video games, filtering spam out of your email and handling a myriad of other tasks, each one specialized for its particular chore.  

Therein lies the rub, each AI needs to be custom built by a programmer specializing in artificial intelligence or machine learning.  In other words, it is currently possible to build machines that learn, but these machines can not learn how to learn.  If we want machines that can truly solve problems, answer questions on their own, and eventually grow to be sentient minds, we need to overcome that obstacle.  

I am joining in on this project and would encourage others interested in Artificial Intelligence to do the same.  Read more about the project at Eric's blog and get involved!

Extending the Range of the Drone

Another fascinating area that I have looked into has been how to extend the range of the drone.  After talking with another ham radio operator, the RFDude, I did some testing on my own.  He gave me a wifi antenna connector platform for me to test with and I built a 2.4 GHz "Cantenna" to try.  A cantenna is literally an antenna made from cans.  Surprisingly, it worked!  I followed these instructions for my build and added an extra can to improve the directionality and hopefully the distance.  Here's some pics after the break