Robot Navigation - A Star Algorithm

Objective

The aim of this lab is to understand the A* algorithm and implement it in Matlab.

1 - Introduction

In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. A* achieves better time performance by using heuristics.

2 - The Algorithm

A* uses a best-first search and finds a least-cost path from a given initial node to the goal node. As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.

It uses a knowledge-plus-heuristic cost function of node x to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:

1. the past path-cost function, which is the known distance from the starting node to the current node x (denoted g(x))
2. a future path-cost function, which is an admissible "heuristic estimate" of the distance from x to the goal (denoted h(x)).

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.

If the heuristic h satisfies the additional condition h(x) = d(x,y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called consistent. In such a case, A* can be implemented more efficiently. No node needs to be processed more than once and. Now let's look at closely to the each steps.

Robot Navigation - The Rotational Sweep Algorithm

Objective

The aim of this post is to understand the rotational plane sweep algorithm to build a visibility graph and implement it in Matlab.

1 - Introduction

The rotational plane sweep is a path planning algorithm based on topological maps. It is one of the most powerful method of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.

2 - The Algorithm

Topological map is a simplified map with only relationship between points. It can be represented as a graph:

• nodes are real positions
• edges join positions in the free space.

They include the distance. It is easy to find a path in a topological map. So, the only problem is how to build a topological map? We are going to create visibility graph.

In order to create visibility graph. We should define for a 2D polygonal configuration space

• The nodes $v_{i}$ of the visibility graph include the start location, the goal location, and all the vertices of the configuration space obstacles. 
• The graph edges $e_{ij}$ are straight-line segments that connect two line-of-sight nodes $v_{i}$ and $v_{j}$, i.e., 

\begin{equation} e_{ij} \neq \emptyset \Longleftrightarrow sv_{i} + (1 - s)v_{j} \in cl(Q_{free}) \forall s \in [0, 1] \end{equation}

Robot Navigation - The Wavefront Planner Algorithm

Hi, reader this report was written for the 'Autonomous Robots' labwork. It explains 'The Wavefront Planner Algorithm'. End of this post, you can see the Matlab codes and also the report itself.

1 - Introduction

The theories behind robot maze navigation is immense. It would take several books just to cover the basics. But this labwork only concentrate on the wavefront planner algorithm which is still powerful methods of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.

2 - The Algorithm

The wavefront algorithm finds a path from point S (start) to point G (goal) through a discretized workspace such as this (0 designates a cell of free space, 1 designates a cell fully occupied by an obstacle):

\[
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 2 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]

Face Recognition

Chapter 1: Introduction

1. Preliminary

In this project, we implemented a face recognition system by using principal component analysis, which is known as PCA. PCA method provide a mathematical way to reduce the dimension of problem.

Since the most elements of a facial image are highly correlated, it is better to extract a set of interesting and discriminative feature of a facial image. Mathematically speaking, we transform the correlated data to independent data. To implement the transform, we employed some linear algebra method such as SVD (Chapter3). The main idea is to obtain Eigenfaces that every face can be regard as a linear combination of these eigenfaces (Chapter4). Then the face recognition problem convert to a mathematic problem: what is the linear combination of a face? In other words, it simplify a problem from 2D to 1D.

Introduction to Spectral Mesh Analysis Toward a simple implementation in C++

Hi reader, as I said before I want to share what I have done and learned from the Vision & Robotics master program. This post includes the our semester project. Actually, the code was given to all the students and the professor wanted us to improve his code and apply 'Spectral Mesh Analysis' on it. You can find more information from the project link that is end of the post. If you have any question free to shoot. I'm just putting here the graphical user interface and how to use the program that is already inside of the project report.

6.1 Framework choice

Because of the constraints that the project must be developed using C++ under Qt IDE, we used the Qt Widgets that are mature and feature rich user interface elements suitable for mostly static user interfaces. Besides, since Qt Widget are native C++ elements it is easier to merge UI with the application logic. The application UI is connected to all other parts of the application through the class Logic. The logic handles all the data interchange between the UI and algorithms. So it is possible to split the application in separate parts.

6.2 Basic elements of UI

The UI is straightforward and easy to use. There are two main parts – openGL screen and sidebar. It is possible to extract many cases of the application usage from the task:

• Load of the file
• Adjust the camera properties
• Adjust the light properties
• Adjust the displaying mode
• Calculate Laplacian Matrix and set new colors according to it
• Find the shortest path from one node to another

How Google ranks Web pages?

Google’s search algorithm combined precomputed PageRank scores with text matching scores to obtain an overall ranking score for each webpage. The PageRank algorithm assigns a PageRank score to each webpages. The algorithm models the behavior of an idealized random Web surfer [1, 2]. This Internet user randomly chooses a webpage to view from the listing of available webpages. Then, the surfer randomly selects a link from that webpage to another webpage.

The model the activity of the random Web surfer, the PageRank algorithm represents the link structure of the Web as a directed graph.

The process for determining PageRank begins by expressing the directed Web graph as the nxn hyperlink matrix, H, where n is the number of webpages.

Real Time Adaptive Shortest Path Navigation System - [Proje]

1 – PROJECT OVERVIEW

This document includes the project proposal for the RETINA(REal Time Adaptive Shortest Path Navigation System) that will be produced at end of fall semester. The schedule for this project starts in September 2012 and ends in January 2013. This project will be developed by the students who are taking CE 497 Senior Project 1 course. The members of this project are as follows:

• Taner Güngör
• Efe Sezer
• Uğur Eryüzlü
• Ulaş Göde

Project will be supervised by Asst. Prof. Süleyman Kondakçı and project coordinator is Taner Güngör who is elected by the project team.

Real Time Adaptive Shortest Path Navigation System provides a package that is combination of the software and hardware. It performs a shortest path for the agents (who are using this system in their vehicles) in the traffic. The system finds that shortest path according to the specified parameters, such as instantaneous flow, throughput, weather conditions, (rain, humidity, snow) illumination of the roads. The oriented customers for this product are personal and commercial vehicle drivers and commercial transportation companies.

The project scope for the Real Time Adaptive Shortest Path Navigation System will be included embedded boards which are Arduino and ARM. These boards will perform the software operations via sensors which are attached on the Arduino board and show up the shortest path on the screen.

Yaban - Yakup Kadri Karaosmanoğlu [Bam Teli]

Uzun bir süredir aklımda olan fakat hayata geçiremediğim bir başka eylemi bu yazı ile gerçekleştiriyorum. Yeni dizinin adı "Bam Teli". Okuduğunuz kitaplarda kimi bölümler vardır hani, onları okuduğunuz vakit o kitaptan daha fazlasını alamayacağınızı bildiğiniz noktalar. Hem büyük bir sevinç hem de büyük bir hüzündür okuyucu için. Büyük bir sevinçtir çünkü merakla okumaya başladığınız o kitaptan istediğinizi almışsınızdır, büyük bir hüzündür çünkü kitabın geri kalanını okuyacak iştahınızı söndürebilir. İşte bu noktalar o eserin bam telidir. Bu ilk yazıda Yakup Kadri Karaosmanoğlu'nun yazdığı Türk edebiyatında aydın-halk arasındaki uçurumu açık ve kaygıdan uzak şekilde ele alan nadir romanlardan biridir. Bu romanın bam teli olduğunu düşündüğüm noktaları aşağıdaki pasajlar:

"Light's Out" Game and Its Solution with Linear Algebra

Hi reader, this is my first article that is written in English here. Why I am writing in English? Actually, I want to share my reports and projects that I found interesting during the master. All reports and projects are of course in English. So, I don't want to translate these subject to Turkish. If you don't know English but want to learn more about. You can ask everything about the related subject. Today, I am going to talk about "Light's Out" game and its solution with "Linear Algebra". If you know Linear Algebra and how to apply it to the game, then it is just 10-15 lines of code. I am also going to share the MATLAB solution end of the article.

Chapter 1: Abstract

1. Preliminary

Light out is a game introduced by tiger electronics, an American toy manufacturer, on a 5 by grid matrix, where each matrix can have either on or off status? The game begins with some of the matrices turned on randomly. Pressing a single buttons will affect the status of itself and its neighbors. The game of the game is to systematically press as much as possible less number of times and making every matrices become off.[1][2]

The goal of the game is to turn all of the lights off. The goal of the puzzle is to switch all the lights off, preferably in as few button presses as possible. Every time a button is pressed, the state of that button as well as the state of the buttons above, below and to the left and right are changed. For example, if all buttons are turned off and a button is pressed, the resulting outcome could result in three, four, or five buttons lighting up depending upon where the original button was located on the game board.[4]

Disket Sürücüsü ile Müzik Çalmak

Herkese merhaba, ilk defa üniversite son sınıftayken youtube üzerinde gördüğüm floopy diskler(disket sürücü) ile müzik çalma işlemini uzun zamandır yapmak istiyordum. Bugün bahsedeceğim konu bu. Hatta yaklaşık 3 ay gibi bir süre Hermes İletişim'de part-time çalıştığım vakit, bu konuyu anlattığım ve aramızda ilk önce kim yapacak diye ufak bir iddiaya tutuştuğum Aşkın Yollu'ya armağan ediyorum bu yazıyı. Öncelikle ihtiyacımız olan malzemelerin listesini vereyim.

1 - Arduino UNO

2 - Kullanılmayan Bir Disket Sürücüsü (Yazıda 3.25 inchlik 34-pine sahip sürücü kullanıyorum, birden fazla kullanabilirsiniz)

3 - Kullanılmayan Bir ATX Güç Kaynağı (Şart değil, gereken akımı Arduino üzerinden de alabilirsiniz)

4 - CAT5 UTP Kablolar (Sürücü ve Arduino arasındaki bağlantılar için)

5 - Breadboard

Yukarıdaki malzemelerimiz tam ise, sürücümüzü müzik çalar hale getirmeye başlayabiliriz. Öncelikle eğer güç kaynağı kullanacaksanız, güç kaynağımızın aşağıdaki resimde görüldüğü gibi yeşil ve herhangi bir siyah kablosunu kısa devre yaptırıyoruz. Bu sayede güç kaynağımız sabit 5 voltluk bir enerji verecektir. Bu enerji ise disket sürücüsünü çalıştırmak için yeterlidir.