Test Log

// TERRAIN PARAMETERS
// Seed Value is passed as an argument to srand(unsigned int)
567

// Roughness Constant for height displacement (.1 to .99)
.2

// Terrain Size (Integer: MAX 2049)
65

// Scales in metres of along the plane
25

// Scale in metres along height axis
1

// BOT PARAMETERS
// Bot Max no of steps (unsigned int)
// Bot run will be discontinued after this many iterations for stuck bots
2500

// Bot Starting X Pos (Should be in the range [0, TerrainSize - 1]
0

// Bot Starting Y Pos (Should be in the range [0, TerrainSize - 1]
0

// Bot Target X Pos (Should be in the range [0, TerrainSize - 1]
64

// Bot Target Y Pos (Should be in the range [0, TerrainSize - 1]
64

// Maximum slope that bot can traverse (absolute value)
// Floating pt angle in degrees (0, 90)
45

Testing with variable RANGE (1 - TerrainSize).

Distance covered seems to be directly proportional to RANGE. HELP!!!. Here's some data :(

RANGE (Cells) - Distance (m)

1 - 2836
2 - 3169
5 - 3298
10 - 2701
15 - 2792
19 - 2686
20 - 2586
21, 22 - 2565
23 - 2665
24, 25, 26 - 2645
27 - 2715
32 - 2707
41 - 2486
42 - 2465 <---------- WTF!!!
45 - 2468
50 - 2468
55 - 2468
MAX - 2468

Collecting my thoughts...

Didn't work the whole day yesterday. Couldn't figure out a simple way to figure out visibility of a cell. I looked at it from both points of view, but still couldn't think of an easy way out.

Then I thought, why not simple draw a straight line? The line-drawing algorithm occurred to me. I searched for Bresenham, and found this. Now I've written a function, which calculates visibility of a cell with respect to the another, completely ignoring cells which come in the way partially. Have to repeat this for all cells within max-range for bot to get good view of the countryside.

How am I representing bot perception of terrain? There are various kinds of terrain - explored/unexplored, passable/unpassable, visible/invisible etc. Anyway here follows the first few steps of the bot:

Basic Algo

* First thing to do would be calculate visibility matrix of surrounding area
* From that matrix, all visible cells, will be deemed explored
* A heuristic function will determine a target cell (explored) within this range (or within all the explored area...yet to be decided). This function should take into account the height of the cells too (since greater height will obviously help see more cells).
* Distance Transform will be performed taking all unexplored cells as impassable (taking worst case)
* Shortest path to target cell will be calculated. If found then bot will use the path to get to that cell, marking all cells on the way as visited. If path is not found then bot will try and move in the default direction of the target one cell at a time and re-run all the previous steps.

To be noted

* Cells once visited will need to have higher cost/heuristic value to discourage repeated visitations.
* Range one as mentioned before, is equivalent to FirstAgent and will be run as this.

Basically work is needed primarily on bot algo. Have to BBS Milda's program too to show that I haven't wasted my time completely with terrain generation. Till I figure something else out, or face steeper terrain...

Final Assignment

Still not having implemented the ranged bot on the terrain, I now have to implement the mofo with some line of sight. Yes, the word you are looking for is YIKES!!! And I only have myself to blame. Jotwani was happy with a satellite which told you everything there was to tell. I, like the stupid dork that I am, had to butt in and suggest this shit. Needless to say, it was an offer he couldn't refuse...just as long as "You should be enjoying what you are doing...that is all that matters". Sheesh! I now need a PC with network almost 24/7, and resources are becoming less accesible now. The only bright side is that I am to submit the report by the morning of 5th May instead of the 1st. Onto more technical issues...

A refresher

If bot's range is just 1 then it is equivalent to the FirstAgent and hence it will do normal brute force search, without a care for the shortest path (will work on this if I have the time. Which means I won't). If on the other hand, its range is more than it will find target cell within range of vision using heuristic from Amit's page, and find shortest path to it. Repeat this cycle till target is reached.

The job now

First and foremost is to find out what the bot can and cannot see. I'll try to be as least sophisticated as possible and hence I'll be taking cell-sized elevations/obstacles. Basically, I'll draw a line tangential to an obstacle. If the line covers more than half the area of the square then the bot's pretty much blind to it. It's not as easy as it sounds, not for me, not now (I hate thinking algorithms under deadlines).

For the bot, I'll keep another boolean visible variable to perform AND operation with. Default cost of unknown cell will be well....default i.e. unpassable. If I take elevation into account then I'd have more problems. More on bot movement algos later. First I gotta implement the mechanics of vision. And also think of a better algorithm for the vanilla ranged hopper so that it utilizes already explored terrain, and stops getting stuck.

XTREME PANIC !!!!

Murphy's BACK!!! and he's banging some serious A$$!! I wake up this morning, reasonably certain that I can complete the minimum requirements of this project by the weekend (and begin the report), and then suddenly like an unholy bolt of lightning ... it strikes!

After implementing the hopper in an naively simple boolean map, I thought I could just copy/paste the code onto the main Bot module, run it and save the world (or atleast my BTP), but not to be. It's a goddamn terrain for god's sakes! An obstacle is only an obstacle with relation to the nearest cells. It might be an obstacle with respect to the cell to the north but perfectly traversible from the NW or NE sides. DAMN, I SUCK! Now I have to write my own Distance Transform method (not much time remaining either). And the fun really begins if I try to implement even an unrealistic square range of vision with obstacles blocking it. There'll be two types of obstacles, one which you could probably see through(like any downward slope) and then of course there are the normal elevated obstacles. And then I'll have to modify the heuristics too to take into the account the changes in the range of vision at different heights. Help them, God, for these hoppers know not what they do.

They are pretty much on a highway to Hell! :'(

Update

Implemented a makeshift algorithm for my ranged vision hoppers. Bot uses a basic heuristic (for diagonal movement on grid map) from Amit Patel's A* heuristics page to calculate the target cell within the range of vision. It then tries to find shortest path to the cell, and then move along that path. If no path is found then the bot will try and move in the default direction of the global target and then again try and find a path to (a new probably) target cell. Yes, not very bright. A better algorithm is needed and fast. Gotta meet him this week ASAP.

Ranged-vision hoppers

Reading a thesis paper on Map exploration and path planning through sonar sensor. Learnt about something knowna as the distance transform which might come in handy for calculating short paths to cells within the range of vision.

THe first problem is to decide the target cell within the range of vision. Should it be at the edge (in which case, I have only about half an idea about the place im hitting), or just before it (which could screw up the utility of the an already small range). And how dynamic should that target cell be (how fast do I update it as the bot hops).

As for the heuristic I was thinking of using some simple function, which are generally used with grid-maps for methods like A*. Amit Patel's heuristic page is pretty ok, and so is this for learning A*, and then this (Link to primary site) for learning about heuristics. In fact, Amit's page should be read after these two.

Post meeting

My current assignment, after meeting with the Prof., is to show through experiments with my program(s), that increased range (i.e. better sensing, costlier apparatus) will lead to more efficient performance (lesser no of steps in this case) by the bot. So much for impressing the BTP panel. Any other improvements are pretty much ruled out until I have crash-tested my bot for this.

Finally I reach a milestone

Yes, the February milestone had now been reached, only about 5 weeks behind schedule. A really dumb agent which does a brute force search (DFS) is now ready. I added colored gradients to bitmaps, which doesn't look as cool as I thought it would look (maybe im using the wrong colors). Going to meet mentor tomorrow to tell him my ram kahani of 2 wasted months (out of a grand total of four).

The question is what do I do now? (Given that a report is required within 20 days). Should I extend the agents vision to give it more ability to do path planning, or should I make movement realistic. In the last meeting, he asked me to find out about what real-world sensors on autonomous rovers are like (for path-planning/navigation). Didn't find out much. I personally want to improve my generated terrains (using some interpolation/smoothing or maybe even Perlin noise) but god knows how little time I have left. I'm also in a quandary whether to implement vehicle motion or stick to my grid hopping bot.

Currently going through a few papers/articles on Mars Rover technology (pretty advanced if you ask me)

The auto-navigation system takes pictures of the nearby terrain using one of the Mars Exploration Rover stereo camera pairs (body-mounted hazard-avoidance cameras on Spirit, mast-mounted navigation cameras on Opportunity). After stereo images are taken, 3-D terrain maps are generated automatically by the rover software. Traversability and safety is then determined from the height and density of rocks or steps, excessive tilts and roughness of the terrain. Dozens of possible paths are considered before the rover chooses the shortest, safest path toward the programmed geographical goal. The rover then drives between 0.5 and 2 meters (1.6 and 6.6 feet) closer to its goal, depending on how many obstacles are nearby. The whole process repeats until it either reaches its goal, or is commanded to stop.

from this article on the Mars Rover site @ JPL, NASA

Lets see what Prof says tomorrow