astar.cpp
Go to the documentation of this file.
00001 /*********************************************************************
00002  *
00003  * Software License Agreement (BSD License)
00004  *
00005  *  Copyright (c) 2008, 2013, Willow Garage, Inc.
00006  *  All rights reserved.
00007  *
00008  *  Redistribution and use in source and binary forms, with or without
00009  *  modification, are permitted provided that the following conditions
00010  *  are met:
00011  *
00012  *   * Redistributions of source code must retain the above copyright
00013  *     notice, this list of conditions and the following disclaimer.
00014  *   * Redistributions in binary form must reproduce the above
00015  *     copyright notice, this list of conditions and the following
00016  *     disclaimer in the documentation and/or other materials provided
00017  *     with the distribution.
00018  *   * Neither the name of Willow Garage, Inc. nor the names of its
00019  *     contributors may be used to endorse or promote products derived
00020  *     from this software without specific prior written permission.
00021  *
00022  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00023  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00024  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00025  *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
00026  *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00027  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00028  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00029  *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00030  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00031  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00032  *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00033  *  POSSIBILITY OF SUCH DAMAGE.
00034  *
00035  * Author: Eitan Marder-Eppstein
00036  *         David V. Lu!!
00037  *********************************************************************/
00038 #include<global_planner/astar.h>
00039 #include<costmap_2d/cost_values.h>
00040 
00041 namespace global_planner {
00042 
00043 AStarExpansion::AStarExpansion(PotentialCalculator* p_calc, int xs, int ys) :
00044         Expander(p_calc, xs, ys) {
00045 }
00046 
00047 bool AStarExpansion::calculatePotentials(unsigned char* costs, double start_x, double start_y, double end_x, double end_y,
00048                                         int cycles, float* potential) {
00049     queue_.clear();
00050     int start_i = toIndex(start_x, start_y);
00051     queue_.push_back(Index(start_i, 0));
00052 
00053     std::fill(potential, potential + ns_, POT_HIGH);
00054     potential[start_i] = 0;
00055 
00056     int goal_i = toIndex(end_x, end_y);
00057     int cycle = 0;
00058 
00059     while (queue_.size() > 0 && cycle < cycles) {
00060         Index top = queue_[0];
00061         std::pop_heap(queue_.begin(), queue_.end(), greater1());
00062         queue_.pop_back();
00063 
00064         int i = top.i;
00065         if (i == goal_i)
00066             return true;
00067 
00068         add(costs, potential, potential[i], i + 1, end_x, end_y);
00069         add(costs, potential, potential[i], i - 1, end_x, end_y);
00070         add(costs, potential, potential[i], i + nx_, end_x, end_y);
00071         add(costs, potential, potential[i], i - nx_, end_x, end_y);
00072     }
00073 
00074     return false;
00075 }
00076 
00077 void AStarExpansion::add(unsigned char* costs, float* potential, float prev_potential, int next_i, int end_x,
00078                          int end_y) {
00079     if (potential[next_i] < POT_HIGH)
00080         return;
00081 
00082     if(costs[next_i]>=lethal_cost_ && !(unknown_ && costs[next_i]==costmap_2d::NO_INFORMATION))
00083         return;
00084 
00085     potential[next_i] = p_calc_->calculatePotential(potential, costs[next_i] + neutral_cost_, next_i, prev_potential);
00086     int x = next_i % nx_, y = next_i / nx_;
00087     float distance = abs(end_x - x) + abs(end_y - y);
00088 
00089     queue_.push_back(Index(next_i, potential[next_i] + distance * neutral_cost_));
00090     std::push_heap(queue_.begin(), queue_.end(), greater1());
00091 }
00092 
00093 } //end namespace global_planner


global_planner
Author(s): David Lu!!
autogenerated on Wed Aug 2 2017 03:13:12