ompl/geometric/src/HillClimbing.cpp
00001 /*********************************************************************
00002 * Software License Agreement (BSD License)
00003 *
00004 *  Copyright (c) 2008, Willow Garage, Inc.
00005 *  All rights reserved.
00006 *
00007 *  Redistribution and use in source and binary forms, with or without
00008 *  modification, are permitted provided that the following conditions
00009 *  are met:
00010 *
00011 *   * Redistributions of source code must retain the above copyright
00012 *     notice, this list of conditions and the following disclaimer.
00013 *   * Redistributions in binary form must reproduce the above
00014 *     copyright notice, this list of conditions and the following
00015 *     disclaimer in the documentation and/or other materials provided
00016 *     with the distribution.
00017 *   * Neither the name of the Willow Garage nor the names of its
00018 *     contributors may be used to endorse or promote products derived
00019 *     from this software without specific prior written permission.
00020 *
00021 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00022 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00023 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00024 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
00025 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00026 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00027 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00028 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00029 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00031 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00032 *  POSSIBILITY OF SUCH DAMAGE.
00033 *********************************************************************/
00034 
00035 /* Author: Ioan Sucan */
00036 
00037 #include "ompl/geometric/HillClimbing.h"
00038 
00039 namespace ompl
00040 {
00041     namespace magic
00042     {
00043 
00048         static const unsigned int MAX_CLIMB_NO_UPDATE_STEPS = 10;
00049     }
00050 }
00051 
00052 bool ompl::geometric::HillClimbing::tryToImprove(const base::GoalRegion &goal, base::State *state, double nearDistance, double *betterGoalDistance) const
00053 {
00054     double tempDistance;
00055     double initialDistance;
00056 
00057     bool wasValid = valid(state);
00058     bool wasValidStart = wasValid;
00059 
00060     bool wasSatisfied = goal.isSatisfied(state, &initialDistance);
00061     bool wasSatisfiedStart = wasSatisfied;
00062 
00063     double bestDist = initialDistance;
00064 
00065     base::StateSamplerPtr ss = si_->allocStateSampler();
00066     base::State *test = si_->allocState();
00067     unsigned int noUpdateSteps = 0;
00068 
00069     for (unsigned int i = 0 ; noUpdateSteps < magic::MAX_CLIMB_NO_UPDATE_STEPS && i < maxImproveSteps_ ; ++i)
00070     {
00071         bool update = false;
00072         ss->sampleUniformNear(test, state, nearDistance);
00073         bool isValid = valid(test);
00074         bool isSatisfied = goal.isSatisfied(test, &tempDistance);
00075         if (!wasValid && isValid)
00076         {
00077             si_->copyState(state, test);
00078             wasValid = true;
00079             wasSatisfied = isSatisfied;
00080             update = true;
00081         }
00082         else
00083             if (wasValid == isValid)
00084             {
00085                 if (!wasSatisfied && isSatisfied)
00086                 {
00087                     si_->copyState(state, test);
00088                     wasSatisfied = true;
00089                     update = true;
00090                 }
00091                 else
00092                     if (wasSatisfied == isSatisfied)
00093                     {
00094                         if (tempDistance < bestDist)
00095                         {
00096                             si_->copyState(state, test);
00097                             bestDist = tempDistance;
00098                             update = true;
00099                         }
00100                     }
00101             }
00102         if (update)
00103             noUpdateSteps = 0;
00104         else
00105             noUpdateSteps++;
00106     }
00107     si_->freeState(test);
00108 
00109     if (betterGoalDistance)
00110         *betterGoalDistance = bestDist;
00111     return (bestDist < initialDistance) || (!wasSatisfiedStart && wasSatisfied) || (!wasValidStart && wasValid);
00112 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines