Now for the Pathfinding

03.22.2015

The A-star is not too complicated, I found the following video series the most helpful in understanding how the algorithm works, thank you Dooobs (3part video) https://www.youtube.com/watch?v=Kw8AMmyc6vg.

This video was pretty useful too, https://www.youtube.com/watch?v=KNXfSOx4eEE

But I personally liked the wiki page on a-star. It was quite comprehensive and detailed. http://en.wikipedia.org/wiki/A*_search_algorithm

I came up with the following psudo code for my a-star pathfinding.

Get open list and closed list

Get the start and end positions

Get the map information.

Put the start position into the open list

While loops while open list is not empty

                Set the current node to the tile with the lowest f in the open list

                Add the current node to the closed list

                Remove the current node from the open list

                If closed list contains neighbour node do nothing

                                If neighbour is walkable               

                                                If neighbour is in open list

                                                                Add parant info for that neighbour

                                                If neighbour is not in open list

                                                                Calculate f,h,g and parant info and add that neighbour to open list

End while loop

But before jumping into the pathfinding code I need to make sure that I can display what I have. To start, I want to keep the map generation separate. This way we can attach different maps, or later if we come up with a better way for generating the 2d matrix we can use that. For this I wrote a simple matlab function.

function [ a] = testmap ()

a=[ 2 -1 0 0 0;

    0 -1 0 -1 0;

    0 -1 0 -1 0;

    0 -1 0 -1 0;

    0  0 0 -1 3];

end

so now whenever I call testmap(), I will get this matrix. I can also tinker with this map without worry as its separate from the rest of the code. Currently its very simplistic but we can build it us as we progress. For now we need a way to display what we are looking at. For that too I will have a function that is modular.it can be replaced and or modified without messing with the other pieces of the code.

Of the many plot/ draw functions in matlab, ‘pcolor’ seems to be the best suited for this, but it does not draw the last column and last row. For this I am going to fix it by adding a dummy column and dummy row.

function [  ] = DrawMap( matrix )

%Draw the grid using pcolor function

%   since the function pcolor does not draw the last row and column

%   i create a dummy row and column just to draw and display on the screen

matrix(6,6)=0;

pcolor(matrix)

end

At this point I know that I would like to use animations and I have yet to find any for the pcolor function, but I think we can change the way we draw it later.

Now we need a main function that will put all the functions together. In this we will need to have a set current pos and set destination functions.

function [  ] = MainFunc( )

%Main function, all other functions will be executed from here

%   Detailed explanation goes here

MapGrid=testmap();

%set current position

MapGrid(1,1)=-2;

%set destination

MapGrid(5,5)=2;

MapGrid

end

and a screenshot of what I get

its small here but we can always make it a larger grid

Getting in to the actual simulation part

03.15.2015

Continuation of the MES tutorial, but by now I have an idea of what matlab can do, and how I want to represent my simulation. I want to model the map that pedestrians will traverse as a grid. The things on the map like buildings obstacles and shops etc. will be represented as numbers in the grid. And the walkable area will also be represented as numbers in the grid. I am thinking to make all non-walkable cell/tile/node a positive number. That way I can represent more things and still keep the node walkable.

Pedestrians will have characteristics based on who they are. Some basic types of characters suggested by my adviser is tourist, office worker, school kid, teenager, and elderly. The model can also include time of day which will dictate what types of people are out and about. For example during school hours on a week day its we are unlikely to find kids and teenagers on the road, and more likely to find tourists. Also at the beginning of the working day and at the close of a working day, we are more likely to find office workers out and about.

So the 1^st step is to get a 2d grid as a map and have a pedestrian/number navigate through obstacles. We need to make it in such a way that the pedestrian’s behaviour/ decision making can be sassily inserted into the code. For the navigation I will use the A-star algorithm as suggested by my adviser. In addition I need to show what I have visually through matlab. Ideally have it animate the data of navigation. So in the next week I will be looking at details on the a-star and how to code it.

I have to write a proposal for this too.

Research and reading

03.01.2015

One major thing I found in the last week is that uk.mathworks.com is a pretty awesome website. It basically has all my questions on matlab answered (to date). Mathworks has some video tutorials but they are pretty basic. I found the MIT video lectures on matlab quite useful

http://ocw.mit.edu/courses/mathematics/18-s997-introduction-to-matlab-programming-fall-2011/library/videos/

this one was very helful in getting started, http://www.phon.ucl.ac.uk/courses/spsci/matlab/

there is a nice set of video tutorials on matlab programming https://www.youtube.com/watch?v=Y5KTmx--ckY though by video 17 it starts on Simulink. That’s more of the engineer’s design element in matlab.

I am also following this tutorial along, http://www.mes.edu.mn/files/matlab_tutorial.pdf Lots of reading, but for this simulation understanding how matlab works is essential.

Presentation due

02.21.2015

Worked on the interim presentation for MSP course, due on Tuesday 20.24.2015

Progress log

out of habit I maintained a progress log for my research, so my blog will be of my progress log and thoughts.

02.20.2015

The 1sat thing to figure out is which tools to use for the simulation. In this case the answer is matlab to do this, as prescribed by my adviser for this project Dr. Vasilli. Before I start thinking about the details of this simulation I need to figure out the things that I should have in the back of my mind as I develop the code and other related material. I need to make sure that at the end of the day my simulation will answer the original question that I started out with. Also this is important because, having the big picture in mind will make development more efficient and likely speed up the process.

So what’s the big picture? A past student of Kingston University has developed a program in unity that will allow the comparison of pedestrian simulation with real world situation through the comparison of real video footage. So what we want to do is develop a simulation that can be used to generate the simulated data to be compared with the real life footage. So all the stuff from here on out will be to develop tools and techniques to get to this stage. There are many useful attractive things to de done with pedestrian simulation and I must be careful not to get distracted by that and keep focus.

So where to start? And easy question to ask, not so easy to answer. I have used matlab for some projects and analysis techniques for my undergraduate degree, but I do not have any experience in programming in matlab, so my 1^st order of business is to figure out what are the tools I have to work with, what can matlab do, what to I need to learn in matlab to get started, and how will I use the tools in matlab to represent the simulation. My initial thoughts are to go try out some matlab tutorials.

1st Two Weeks

We learned about agile sprint and did a mock project using the techniques we learned. some pictures from week below. The group I worked with were really cool and I enjoyed working with them.