View unanswered posts | View active topics It is currently Fri Apr 18, 2014 10:04 pm






Reply to topic  [ 31 posts ]  Go to page 1, 2, 3  Next
Heuristic algorithm 
Author Message
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Heuristic algorithm
Hi, i'm a computer science major in AI student . I'm still new using RobotC and NXT.

i were given project to build a mobile or rescue robot implemented with Heuristic algorithm ( One of AI field).
i'm still got some lack knowledge on engineering part.

right i don't have an idea how to combine this both.i'm only know do simple program using RobotC.

this are some of algorithm i need to test, but only need to choose 1 or 2

Hill climbing
Genetic Algorithms
Reinforcement Learning
Generate-and-test
Simulated annealing
Greedy search
Dijkstra's algorithm


can some one give me an idea where should i start?


Thu Mar 14, 2013 10:48 pm
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: Heuristic algorithm
Quote:
can some one give me an idea where should i start?

Try making your robot move and read from a sensor. Once you get the hang of that, read up on the other stuff. Here's some stuff to get you started: http://www.robotc.net/education/curriculum/nxt/
You can also find a number of tutorials on my site, but they may be a little advanced at this stage: http://botbench.com/blog/category/tutorials/

= Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Fri Mar 15, 2013 4:31 pm
Profile WWW
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
mightor wrote:
Quote:
can some one give me an idea where should i start?

Try making your robot move and read from a sensor. Once you get the hang of that, read up on the other stuff. Here's some stuff to get you started: http://www.robotc.net/education/curriculum/nxt/
You can also find a number of tutorials on my site, but they may be a little advanced at this stage: http://botbench.com/blog/category/tutorials/

= Xander


thanks...


Fri Mar 15, 2013 9:34 pm
Profile
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
i'm now already understand a bit how to use sensor and simple coding.

so i want ask some opinion how many sensor i should use and type.

i'm try to do auto searching and retrieve then implement with A* algorithm to make it more efficient.

if anyone have basic maze simple coding would you mind share it?

i want to study it a bit then implement with my A* algorithm.

your help i'm really appreciate it. :)

p/s: i'm attach the picture of maze or map i create. Right now using ranger bot with arm and griper design.


Attachments:
2013-04-24 13.41.23.jpg
2013-04-24 13.41.23.jpg [ 601.43 KiB | Viewed 3347 times ]
Fri Apr 26, 2013 12:12 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: Heuristic algorithm
A simple follow the wall on the left will solve this maze :)

= Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Fri Apr 26, 2013 7:28 am
Profile WWW
Expert

Joined: Thu Jan 03, 2013 5:10 pm
Posts: 186
Location: The plateau north of the Ohio River Valley, also known as Cave Country.
Post Re: Heuristic algorithm
The sensor type I would use is a distance sensor, such as the ultrasonic. One will do, but will be required to rotate to see the walls from each new vantage point.

_________________
I'm not a robot! I'm british! ~ quote from an asparagus
I am not a robot! I am a unicorn! ~ quote from a robot
Play chess for free!


Fri Apr 26, 2013 8:08 pm
Profile
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
mightor wrote:
A simple follow the wall on the left will solve this maze :)

= Xander


thanks

Coder A wrote:
The sensor type I would use is a distance sensor, such as the ultrasonic. One will do, but will be required to rotate to see the walls from each new vantage point.


that meant i need to make the sonar sensor rotate at certain point?

in case i put a bottle 500ml in certain place in this map
but how to determine an object to pick it up?

it one sensor would be enough?


Fri Apr 26, 2013 10:33 pm
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: Heuristic algorithm
I am a big fan of IR Sensors, like the DistNX from Mindsensors: [LINK]. It is less prone to erroneous readings, in my experience. Take a look at this really highly detailed picture of pure scientific awesomeness (made with Paint).
Attachment:
IRscanProfile.jpg
IRscanProfile.jpg [ 41.09 KiB | Viewed 3306 times ]

You can detected the object by looking for a big, sudden dip in the distances measured. straight ahead of you. You do expect some decrease in distance as your angle approaches zero but if it is much higher, then perhaps it is worth investigating :)

= Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Sat Apr 27, 2013 2:01 am
Profile WWW
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
mightor wrote:
I am a big fan of IR Sensors, like the DistNX from Mindsensors: [LINK]. It is less prone to erroneous readings, in my experience. Take a look at this really highly detailed picture of pure scientific awesomeness (made with Paint).
Attachment:
IRscanProfile.jpg

You can detected the object by looking for a big, sudden dip in the distances measured. straight ahead of you. You do expect some decrease in distance as your angle approaches zero but if it is much higher, then perhaps it is worth investigating :)

= Xander


nice, but my lecture just want me used the only set given :D

buy the way is there any other solution that i can used more sensor on nxt

it only can mount 4 right?

do i need another NXT?

my method is i want use condition
if both sensor detect same high it meant there no object in front. if have then it try to grab it :D

ps: but for my own project it would be nice


Sat Apr 27, 2013 5:55 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: Heuristic algorithm
You can use the Ultrasound sensor instead, if you'd like. You an only use four sensors, that is correct.

= Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Sat Apr 27, 2013 7:57 am
Profile WWW
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
mightor wrote:
You can use the Ultrasound sensor instead, if you'd like. You an only use four sensors, that is correct.

= Xander


thank you very much for help and tips :bigthumb:


Sun Apr 28, 2013 11:29 am
Profile
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
Question
---------
1.When i'm running in visual it run smoothly but when i compile and downloaded to robotRanger the sonar can't detect obstacle or wall in front and sometime after hit the wall then it detect.Why?

2. From front view , left tyres move forward and right tyres move backward.
in the end i have to do this


motor[rightMotor] = speed; // set mtr_S1_C1_1 is run at a power level equal to 'speed'
motor[leftMotor] = -speed; // set mtr_S1_C1_2 is run at a power level equal to 'speed'


Fri May 03, 2013 12:21 am
Profile
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
i already read this link and it forum thread http://www.robotc.net/blog/2011/08/08/r ... -training/
now i have and idea how to start using A* algorithm

when i study the coding and try run the code it came out and error

**Error**:Internal Compiler: Bad source parameter for conversion to 'long' result
**Severe*:Bad opcode for string variable type
**Severe*:Invalid/undefined opcode [Bad]

just to make sure that is the coding were correct or the developer intentionally do the error or my mistake.


Tue Jul 16, 2013 2:33 am
Profile
Professor
User avatar

Joined: Sat May 18, 2013 1:24 pm
Posts: 272
Location: Olympia, WA
Post Re: Heuristic algorithm
To reverse the motors, go into the Motor/Sensor config (double click the #pragma config lines at the top of your code) and check the box next to "Reversed" for the motors which are running backwards (note: this will not reverse encoders, I think).

To see what is going on with the sensor, go to Robot->NXT Brick->Test I2C Sensors Utility to see what is your sensor is returning. I'm speculating here, but you might need to add a `Wait(10);` in your code somewhere.

Could you please post your code here for us to see? Surround your code with [code] //your code here [/code] so it looks nicer.

_________________
FTC Team 6424, the 'Oly Cow - Chief programmer.
FRC Team 4450, Olympia Robotics Federation (ORF).

and also quadrotors. Quadrotors!


Tue Jul 16, 2013 6:50 pm
Profile
Rookie
User avatar

Joined: Thu Mar 14, 2013 10:32 pm
Posts: 25
Location: Malaysia
Post Re: Heuristic algorithm
Ernest3.14 wrote:
To reverse the motors, go into the Motor/Sensor config (double click the #pragma config lines at the top of your code) and check the box next to "Reversed" for the motors which are running backwards (note: this will not reverse encoders, I think).

To see what is going on with the sensor, go to Robot->NXT Brick->Test I2C Sensors Utility to see what is your sensor is returning. I'm speculating here, but you might need to add a `Wait(10);` in your code somewhere.

Could you please post your code here for us to see? Surround your code with
Code:
 //your code here
so it looks nicer.


Thanks,

For motor part already sloved.

Here the code that i get

Code:

//GLOBAL VARIABLES grid world dimensions
const int x_size = 10;
const int y_size = 5;

//GLOBAL ARRAY representation of grid world using a 2-Dimensional array
//0  = open space
//1  = barrier
//2  = goal
//99 = robot
int map[x_size][y_size] =
 {{0,0,0,0,0},
  {0,1,99,1,0},
  {0,1,1,1,0},
  {0,0,0,0,0},
  {0,0,0,0,0},
  {0,0,0,0,0},
  {0,0,0,0,0},
  {0,0,2,0,0},
  {0,0,0,0,0},
  {0,0,0,0,0}};

//FUNCTION move forward for a variable number of grid blocks
void moveForward(int blocks)
{
  //convert number of blocks to encoder counts
  //wheel circumference = 17.6 cm
  //one block = 23.7 cm / 35.cm
  int countsToTravel = (35/17.6)*(360)*blocks;

  //encoder target for countsToTravel
  nMotorEncoder[motorB] = 0;
  nMotorEncoder[motorC] = 0;
  nMotorEncoderTarget[motorB] = countsToTravel;
  nMotorEncoderTarget[motorC] = countsToTravel;
  motor[motorB] = 50;
  motor[motorC] = 50;
  while(nMotorRunState[motorB] != runStateIdle && nMotorRunState[motorC] != runStateIdle) {}

  //stop for half second at end of movement
  motor[motorB] = 0;
  motor[motorC] = 0;
  wait1Msec(500);
}

//FUNCTION left point turn 90 degrees
void turnLeft90()
{
  //distance one wheel must travel for 90 degree point turn = 10.68 cm
  //wheel circumference = 17.6 cm
  int countsToTravel = (8.6/17.6)*(360);

  //encoder target for countsToTravel
  nMotorEncoder[motorB] = 0;
  nMotorEncoder[motorC] = 0;
  nMotorEncoderTarget[motorB] = countsToTravel;
  nMotorEncoderTarget[motorC] = countsToTravel;
  motor[motorB] = 50;
  motor[motorC] = -50;
  while(nMotorRunState[motorB] != runStateIdle && nMotorRunState[motorC] != runStateIdle) {}

  //stop for half second at end of movement
  motor[motorB] = 0;
  motor[motorC] = 0;
  wait1Msec(500);
}

//FUNCTION right point turn 90 degrees
void turnRight90()
{
  //distance one wheel must travel for 90 degree point turn = 10.68 cm
  //wheel circumference = 17.6 cm
  int countsToTravel = (8.6/17.6)*(360);

  //encoder target for countsToTravel
  nMotorEncoder[motorB] = 0;
  nMotorEncoder[motorC] = 0;
  nMotorEncoderTarget[motorB] = countsToTravel;
  nMotorEncoderTarget[motorC] = countsToTravel;
  motor[motorB] = -50;
  motor[motorC] = 50;
  while(nMotorRunState[motorB] != runStateIdle && nMotorRunState[motorC] != runStateIdle) {}

  //stop for half second at end of movement
  motor[motorB] = 0;
  motor[motorC] = 0;
  wait1Msec(500);
}

//FUNCTION print wavefront map to NXT screen
void PrintWavefrontMap()
{
  int printLine = y_size-1;
  for(int y = 0; y < y_size; y++)
  {
    string printRow = "";
    for(int x=0; x < x_size; x++)
    {
      if(map[x][y] == 99)
        printRow = printRow + "R ";
      else if(map[x][y] == 2)
        printRow = printRow + "G ";
      else if(map[x][y] == 1)
        printRow = printRow + "X ";
      else if(map[x][y] < 10)
        printRow = printRow + map[x][y] + " ";
      else if(map[x][y] == '*')
        printRow = printRow + "* ";
      else
        printRow = printRow + map[x][y];
    }
    nxtDisplayString(printLine, printRow);
    printLine--;
  }
}

//FUNCTION wavefront algorithm to find most efficient path to goal
void WavefrontSearch()
{
  int goal_x, goal_y;
  bool foundWave = true;
  int currentWave = 2; //Looking for goal first

  while(foundWave == true)
  {
    foundWave = false;
    for(int y=0; y < y_size; y++)
    {
      for(int x=0; x < x_size; x++)
      {
        if(map[x][y] == currentWave)
        {
          foundWave = true;
          goal_x = x;
          goal_y = y;

          if(goal_x > 0) //This code checks the array bounds heading WEST
            if(map[goal_x-1][goal_y] == 0)  //This code checks the WEST direction
              map[goal_x-1][goal_y] = currentWave + 1;

          if(goal_x < (x_size - 1)) //This code checks the array bounds heading EAST
            if(map[goal_x+1][goal_y] == 0)//This code checks the EAST direction
              map[goal_x+1][goal_y] = currentWave + 1;

          if(goal_y > 0)//This code checks the array bounds heading SOUTH
            if(map[goal_x][goal_y-1] == 0) //This code checks the SOUTH direction
              map[goal_x][goal_y-1] = currentWave + 1;

          if(goal_y < (y_size - 1))//This code checks the array bounds heading NORTH
            if(map[goal_x][goal_y+1] == 0) //This code checks the NORTH direction
              map[goal_x][goal_y+1] = currentWave + 1;
        }
      }
    }
    currentWave++;
    PrintWavefrontMap();
    wait1Msec(500);
  }
}

//FUNCTION follow most efficient path to goal
//and update screen map as robot moves
void NavigateToGoal()
{
  //Store our Robots Current Position
  int robot_x, robot_y;

  //First - Find Goal and Target Locations
  for(int x=0; x < x_size; x++)
  {
    for(int y=0; y < y_size; y++)
    {
      if(map[x][y] == 99)
      {
        robot_x = x;
        robot_y = y;
      }
    }
  }

  //Found Goal and Target, start deciding our next path
  int current_x = robot_x;
  int current_y = robot_y;
  int current_facing = 0;
  int next_Direction = 0;
  int current_low = 99;

  while(current_low > 2)
  {
    current_low = 99; //Every time, reset to highest number (robot)
    next_Direction = current_facing;
    int Next_X = 0;
    int Next_Y = 0;

    //Check Array Bounds West
    if(current_x > 0)
      if(map[current_x-1][current_y] < current_low && map[current_x-1][current_y] != 1) //Is current space occupied?
    {
      current_low = map[current_x-1][current_y];  //Set next number
      next_Direction = 3; //Set Next Direction as West
      Next_X = current_x-1;
      Next_Y = current_y;
    }

    //Check Array Bounds East
    if(current_x < (x_size -1))
      if(map[current_x+1][current_y] < current_low && map[current_x+1][current_y] != 1) //Is current space occupied?
    {
      current_low = map[current_x+1][current_y];  //Set next number
      next_Direction = 1; //Set Next Direction as East
      Next_X = current_x+1;
      Next_Y = current_y;
    }

    //Check Array Bounds South
    if(current_y > 0)
      if(map[current_x][current_y-1] < current_low && map[current_x][current_y-1] != 1)
    {
      current_low = map[current_x][current_y-1];  //Set next number
      next_Direction = 2; //Set Next Direction as South
      Next_X = current_x;
      Next_Y = current_y-1;
    }

    //Check Array Bounds North
    if(current_y < (y_size - 1))
      if(map[current_x][current_y+1] < current_low && map[current_x][current_y+1] != 1) //Is current space occupied?
    {
      current_low = map[current_x][current_y+1];  //Set next number
      next_Direction = 0; //Set Next Direction as North
      Next_X = current_x;
      Next_Y = current_y+1;
    }

    //Okay - We know the number we're heading for, the direction and the coordinates.
    current_x = Next_X;
    current_y = Next_Y;
    map[current_x][current_y] = '*';

    //Track the robot's heading
    while(current_facing != next_Direction)
    {
      if (current_facing > next_Direction)
      {
        turnLeft90();
        current_facing--;
      }
      else if(current_facing < next_Direction)
      {
        turnRight90();
        current_facing++;
      }
    }
    moveForward(1);
    PrintWavefrontMap();
    wait1Msec(500);
  }
}

task main()
{
  WavefrontSearch();    //Build map of route with wavefront algorithm
  NavigateToGoal(); //Follow most efficient path to goal
  wait1Msec(5000);  //Leave time to view the LCD screen
}


the message come out is

**Error**:Internal Compiler: Bad source parameter for conversion to 'long' result
**Severe*:Bad opcode for string variable type
**Severe*:Invalid/undefined opcode [Bad]

Another question is why the nxt lego mindstrom won't go straight line without using sensor?

p/s: This is original code. I don't don't change much , i think. Because i want to study it first but the error come out


Wed Jul 17, 2013 5:41 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 31 posts ]  Go to page 1, 2, 3  Next

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.