ompl/geometric/planners/prm/src/LazyPRM.cpp
00001 /********************************************************************* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Copyright (c) 2013, Willow Garage 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 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, Ryan Luna */ 00036 00037 #include "ompl/geometric/planners/prm/LazyPRM.h" 00038 #include "ompl/base/objectives/PathLengthOptimizationObjective.h" 00039 #include "ompl/base/goals/GoalSampleableRegion.h" 00040 #include "ompl/geometric/planners/prm/ConnectionStrategy.h" 00041 #include "ompl/tools/config/SelfConfig.h" 00042 #include <boost/lambda/bind.hpp> 00043 #include <boost/graph/astar_search.hpp> 00044 #include <boost/graph/incremental_components.hpp> 00045 #include <boost/graph/lookup_edge.hpp> 00046 #include <boost/foreach.hpp> 00047 #include <queue> 00048 00049 #include "GoalVisitor.hpp" 00050 00051 #define foreach BOOST_FOREACH 00052 00053 namespace ompl 00054 { 00055 namespace magic 00056 { 00059 static const unsigned int DEFAULT_NEAREST_NEIGHBORS_LAZY = 5; 00060 00064 static const unsigned int MIN_ADDED_SEGMENTS_FOR_LAZY_OPTIMIZATION = 5; 00065 } 00066 } 00067 00068 ompl::geometric::LazyPRM::LazyPRM(const base::SpaceInformationPtr &si, bool starStrategy) : 00069 base::Planner(si, "LazyPRM"), 00070 starStrategy_(starStrategy), 00071 userSetConnectionStrategy_(false), 00072 maxDistance_(0.0), 00073 indexProperty_(boost::get(boost::vertex_index_t(), g_)), 00074 stateProperty_(boost::get(vertex_state_t(), g_)), 00075 weightProperty_(boost::get(boost::edge_weight, g_)), 00076 vertexComponentProperty_(boost::get(vertex_component_t(), g_)), 00077 vertexValidityProperty_(boost::get(vertex_flags_t(), g_)), 00078 edgeValidityProperty_(boost::get(edge_flags_t(), g_)), 00079 componentCount_(0), 00080 bestCost_(std::numeric_limits<double>::quiet_NaN()), 00081 iterations_(0) 00082 { 00083 specs_.recognizedGoal = base::GOAL_SAMPLEABLE_REGION; 00084 specs_.approximateSolutions = false; 00085 specs_.optimizingPaths = true; 00086 00087 Planner::declareParam<double>("range", this, &LazyPRM::setRange, &LazyPRM::getRange, "0.:1.:10000."); 00088 Planner::declareParam<unsigned int>("max_nearest_neighbors", this, &LazyPRM::setMaxNearestNeighbors, std::string("8:1000")); 00089 00090 addPlannerProgressProperty("iterations INTEGER", 00091 boost::bind(&LazyPRM::getIterationCount, this)); 00092 addPlannerProgressProperty("best cost REAL", 00093 boost::bind(&LazyPRM::getBestCost, this)); 00094 addPlannerProgressProperty("milestone count INTEGER", 00095 boost::bind(&LazyPRM::getMilestoneCountString, this)); 00096 addPlannerProgressProperty("edge count INTEGER", 00097 boost::bind(&LazyPRM::getEdgeCountString, this)); 00098 } 00099 00100 ompl::geometric::LazyPRM::~LazyPRM() 00101 { 00102 } 00103 00104 void ompl::geometric::LazyPRM::setup() 00105 { 00106 Planner::setup(); 00107 tools::SelfConfig sc(si_, getName()); 00108 sc.configurePlannerRange(maxDistance_); 00109 00110 if (!nn_) 00111 { 00112 nn_.reset(tools::SelfConfig::getDefaultNearestNeighbors<Vertex>(si_->getStateSpace())); 00113 nn_->setDistanceFunction(boost::bind(&LazyPRM::distanceFunction, this, _1, _2)); 00114 } 00115 if (!connectionStrategy_) 00116 { 00117 if (starStrategy_) 00118 connectionStrategy_ = KStarStrategy<Vertex>(boost::bind(&LazyPRM::milestoneCount, this), nn_, si_->getStateDimension()); 00119 else 00120 connectionStrategy_ = KBoundedStrategy<Vertex>(magic::DEFAULT_NEAREST_NEIGHBORS_LAZY, maxDistance_, nn_); 00121 } 00122 if (!connectionFilter_) 00123 connectionFilter_ = boost::lambda::constant(true); 00124 00125 // Setup optimization objective 00126 // 00127 // If no optimization objective was specified, then default to 00128 // optimizing path length as computed by the distance() function 00129 // in the state space. 00130 if (pdef_) 00131 { 00132 if (pdef_->hasOptimizationObjective()) 00133 opt_ = pdef_->getOptimizationObjective(); 00134 else 00135 { 00136 opt_.reset(new base::PathLengthOptimizationObjective(si_)); 00137 if (!starStrategy_) 00138 opt_->setCostThreshold(opt_->infiniteCost()); 00139 } 00140 } 00141 else 00142 { 00143 OMPL_INFORM("%s: problem definition is not set, deferring setup completion...", getName().c_str()); 00144 setup_ = false; 00145 } 00146 00147 sampler_ = si_->allocStateSampler(); 00148 } 00149 00150 void ompl::geometric::LazyPRM::setRange(double distance) 00151 { 00152 maxDistance_ = distance; 00153 if (!userSetConnectionStrategy_) 00154 connectionStrategy_.clear(); 00155 if (isSetup()) 00156 setup(); 00157 } 00158 00159 void ompl::geometric::LazyPRM::setMaxNearestNeighbors(unsigned int k) 00160 { 00161 if (starStrategy_) 00162 throw Exception("Cannot set the maximum nearest neighbors for " + getName()); 00163 if (!nn_) 00164 { 00165 nn_.reset(tools::SelfConfig::getDefaultNearestNeighbors<Vertex>(si_->getStateSpace())); 00166 nn_->setDistanceFunction(boost::bind(&LazyPRM::distanceFunction, this, _1, _2)); 00167 } 00168 if (!userSetConnectionStrategy_) 00169 connectionStrategy_.clear(); 00170 if (isSetup()) 00171 setup(); 00172 } 00173 00174 void ompl::geometric::LazyPRM::setProblemDefinition(const base::ProblemDefinitionPtr &pdef) 00175 { 00176 Planner::setProblemDefinition(pdef); 00177 clearQuery(); 00178 } 00179 00180 void ompl::geometric::LazyPRM::clearQuery() 00181 { 00182 startM_.clear(); 00183 goalM_.clear(); 00184 pis_.restart(); 00185 } 00186 00187 void ompl::geometric::LazyPRM::clear() 00188 { 00189 Planner::clear(); 00190 freeMemory(); 00191 if (nn_) 00192 nn_->clear(); 00193 clearQuery(); 00194 00195 componentCount_ = 0; 00196 iterations_ = 0; 00197 bestCost_ = base::Cost(std::numeric_limits<double>::quiet_NaN()); 00198 } 00199 00200 void ompl::geometric::LazyPRM::freeMemory() 00201 { 00202 foreach (Vertex v, boost::vertices(g_)) 00203 si_->freeState(stateProperty_[v]); 00204 g_.clear(); 00205 } 00206 00207 ompl::geometric::LazyPRM::Vertex ompl::geometric::LazyPRM::addMilestone(base::State *state) 00208 { 00209 Vertex m = boost::add_vertex(g_); 00210 stateProperty_[m] = state; 00211 vertexValidityProperty_[m] = VALIDITY_UNKNOWN; 00212 unsigned long int newComponent = componentCount_++; 00213 vertexComponentProperty_[m] = newComponent; 00214 componentSize_[newComponent] = 1; 00215 00216 // Which milestones will we attempt to connect to? 00217 const std::vector<Vertex> &neighbors = connectionStrategy_(m); 00218 foreach (Vertex n, neighbors) 00219 if (connectionFilter_(m, n)) 00220 { 00221 const base::Cost weight = opt_->motionCost(stateProperty_[m], stateProperty_[n]); 00222 const Graph::edge_property_type properties(weight); 00223 const Edge &e = boost::add_edge(m, n, properties, g_).first; 00224 edgeValidityProperty_[e] = VALIDITY_UNKNOWN; 00225 uniteComponents(m, n); 00226 } 00227 00228 nn_->add(m); 00229 00230 return m; 00231 } 00232 00233 ompl::base::PlannerStatus ompl::geometric::LazyPRM::solve(const base::PlannerTerminationCondition &ptc) 00234 { 00235 checkValidity(); 00236 base::GoalSampleableRegion *goal = dynamic_cast<base::GoalSampleableRegion*>(pdef_->getGoal().get()); 00237 00238 if (!goal) 00239 { 00240 OMPL_ERROR("%s: Unknown type of goal", getName().c_str()); 00241 return base::PlannerStatus::UNRECOGNIZED_GOAL_TYPE; 00242 } 00243 00244 // Add the valid start states as milestones 00245 while (const base::State *st = pis_.nextStart()) 00246 startM_.push_back(addMilestone(si_->cloneState(st))); 00247 00248 if (startM_.size() == 0) 00249 { 00250 OMPL_ERROR("%s: There are no valid initial states!", getName().c_str()); 00251 return base::PlannerStatus::INVALID_START; 00252 } 00253 00254 if (!goal->couldSample()) 00255 { 00256 OMPL_ERROR("%s: Insufficient states in sampleable goal region", getName().c_str()); 00257 return base::PlannerStatus::INVALID_GOAL; 00258 } 00259 00260 // Ensure there is at least one valid goal state 00261 if (goal->maxSampleCount() > goalM_.size() || goalM_.empty()) 00262 { 00263 const base::State *st = goalM_.empty() ? pis_.nextGoal(ptc) : pis_.nextGoal(); 00264 if (st) 00265 goalM_.push_back(addMilestone(si_->cloneState(st))); 00266 00267 if (goalM_.empty()) 00268 { 00269 OMPL_ERROR("%s: Unable to find any valid goal states", getName().c_str()); 00270 return base::PlannerStatus::INVALID_GOAL; 00271 } 00272 } 00273 00274 unsigned long int nrStartStates = boost::num_vertices(g_); 00275 OMPL_INFORM("%s: Starting planning with %lu states already in datastructure", getName().c_str(), nrStartStates); 00276 00277 bestCost_ = opt_->infiniteCost(); 00278 base::State *workState = si_->allocState(); 00279 std::pair<std::size_t, std::size_t> startGoalPair; 00280 base::PathPtr bestSolution; 00281 bool fullyOptimized = false; 00282 bool someSolutionFound = false; 00283 unsigned int optimizingComponentSegments = 0; 00284 00285 // Grow roadmap in lazy fashion -- add vertices and edges without checking validity 00286 while (ptc == false) 00287 { 00288 ++iterations_; 00289 sampler_->sampleUniform(workState); 00290 Vertex addedVertex = addMilestone(si_->cloneState(workState)); 00291 00292 const long int solComponent = solutionComponent(&startGoalPair); 00293 // If the start & goal are connected and we either did not find any solution 00294 // so far or the one we found still needs optimizing and we just added an edge 00295 // to the connected component that is used for the solution, we attempt to 00296 // construct a new solution. 00297 if (solComponent != -1 && (!someSolutionFound || (long int)vertexComponentProperty_[addedVertex] == solComponent)) 00298 { 00299 // If we already have a solution, we are optimizing. We check that we added at least 00300 // a few segments to the connected component that includes the previously found 00301 // solution before attempting to construct a new solution. 00302 if (someSolutionFound) 00303 { 00304 if (++optimizingComponentSegments < magic::MIN_ADDED_SEGMENTS_FOR_LAZY_OPTIMIZATION) 00305 continue; 00306 optimizingComponentSegments = 0; 00307 } 00308 Vertex startV = startM_[startGoalPair.first]; 00309 Vertex goalV = goalM_[startGoalPair.second]; 00310 base::PathPtr solution; 00311 do 00312 { 00313 solution = constructSolution(startV, goalV); 00314 } while (!solution && vertexComponentProperty_[startV] == vertexComponentProperty_[goalV]); 00315 if (solution) 00316 { 00317 someSolutionFound = true; 00318 base::Cost c = solution->cost(opt_); 00319 if (opt_->isSatisfied(c)) 00320 { 00321 fullyOptimized = true; 00322 bestSolution = solution; 00323 bestCost_ = c; 00324 break; 00325 } 00326 else 00327 { 00328 if (opt_->isCostBetterThan(c, bestCost_)) 00329 { 00330 bestSolution = solution; 00331 bestCost_ = c; 00332 } 00333 } 00334 } 00335 } 00336 } 00337 00338 si_->freeState(workState); 00339 00340 if (bestSolution) 00341 { 00342 base::PlannerSolution psol(bestSolution); 00343 psol.setPlannerName(getName()); 00344 // if the solution was optimized, we mark it as such 00345 psol.setOptimized(opt_, bestCost_, fullyOptimized); 00346 pdef_->addSolutionPath(psol); 00347 } 00348 00349 OMPL_INFORM("%s: Created %u states", getName().c_str(), boost::num_vertices(g_) - nrStartStates); 00350 00351 return bestSolution ? base::PlannerStatus::EXACT_SOLUTION : base::PlannerStatus::TIMEOUT; 00352 } 00353 00354 void ompl::geometric::LazyPRM::uniteComponents(Vertex a, Vertex b) 00355 { 00356 unsigned long int componentA = vertexComponentProperty_[a]; 00357 unsigned long int componentB = vertexComponentProperty_[b]; 00358 if (componentA == componentB) return; 00359 if (componentSize_[componentA] > componentSize_[componentB]) 00360 { 00361 std::swap(componentA, componentB); 00362 std::swap(a, b); 00363 } 00364 markComponent(a, componentB); 00365 } 00366 00367 void ompl::geometric::LazyPRM::markComponent(Vertex v, unsigned long int newComponent) 00368 { 00369 std::queue<Vertex> q; 00370 q.push(v); 00371 while (!q.empty()) 00372 { 00373 Vertex n = q.front(); 00374 q.pop(); 00375 unsigned long int &component = vertexComponentProperty_[n]; 00376 if (component == newComponent) continue; 00377 if (componentSize_[component] == 1) 00378 componentSize_.erase(component); 00379 else 00380 componentSize_[component]--; 00381 component = newComponent; 00382 componentSize_[newComponent]++; 00383 boost::graph_traits<Graph>::adjacency_iterator nbh, last; 00384 for (boost::tie(nbh, last) = boost::adjacent_vertices(n, g_) ; nbh != last ; ++nbh) 00385 q.push(*nbh); 00386 } 00387 } 00388 00389 long int ompl::geometric::LazyPRM::solutionComponent(std::pair<std::size_t, std::size_t> *startGoalPair) const 00390 { 00391 for (std::size_t startIndex = 0; startIndex < startM_.size(); ++startIndex) 00392 { 00393 long int startComponent = vertexComponentProperty_[startM_[startIndex]]; 00394 for (std::size_t goalIndex = 0; goalIndex < goalM_.size(); ++goalIndex) 00395 { 00396 if (startComponent == (long int)vertexComponentProperty_[goalM_[goalIndex]]) 00397 { 00398 startGoalPair->first = startIndex; 00399 startGoalPair->second = goalIndex; 00400 return startComponent; 00401 } 00402 } 00403 } 00404 return -1; 00405 } 00406 00407 ompl::base::PathPtr ompl::geometric::LazyPRM::constructSolution(const Vertex &start, const Vertex &goal) 00408 { 00409 // Need to update the index map here, becuse nodes may have been removed and 00410 // the numbering will not be 0 .. N-1 otherwise. 00411 unsigned long int index = 0; 00412 boost::graph_traits<Graph>::vertex_iterator vi, vend; 00413 for(boost::tie(vi, vend) = boost::vertices(g_); vi != vend; ++vi, ++index) 00414 indexProperty_[*vi] = index; 00415 00416 boost::property_map<Graph, boost::vertex_predecessor_t>::type prev; 00417 try 00418 { 00419 // Consider using a persistent distance_map if it's slow 00420 boost::astar_search(g_, start, 00421 boost::bind(&LazyPRM::costHeuristic, this, _1, goal), 00422 boost::predecessor_map(prev). 00423 distance_compare(boost::bind(&base::OptimizationObjective:: 00424 isCostBetterThan, opt_.get(), _1, _2)). 00425 distance_combine(boost::bind(&base::OptimizationObjective:: 00426 combineCosts, opt_.get(), _1, _2)). 00427 distance_inf(opt_->infiniteCost()). 00428 distance_zero(opt_->identityCost()). 00429 visitor(AStarGoalVisitor<Vertex>(goal))); 00430 } 00431 catch (AStarFoundGoal&) 00432 { 00433 } 00434 if (prev[goal] == goal) 00435 throw Exception(name_, "Could not find solution path"); 00436 00437 // First, get the solution states without copying them, and check them for validity. 00438 // We do all the node validity checks for the vertices, as this may remove a larger 00439 // part of the graph (compared to removing an edge). 00440 std::vector<const base::State*> states(1, stateProperty_[goal]); 00441 std::set<Vertex> milestonesToRemove; 00442 for (Vertex pos = prev[goal]; prev[pos] != pos; pos = prev[pos]) 00443 { 00444 const base::State *st = stateProperty_[pos]; 00445 unsigned int &vd = vertexValidityProperty_[pos]; 00446 if ((vd & VALIDITY_TRUE) == 0) 00447 if (si_->isValid(st)) 00448 vd |= VALIDITY_TRUE; 00449 if ((vd & VALIDITY_TRUE) == 0) 00450 milestonesToRemove.insert(pos); 00451 if (milestonesToRemove.empty()) 00452 states.push_back(st); 00453 } 00454 00455 // We remove *all* invalid vertices. This is not entirely as described in the original LazyPRM 00456 // paper, as the paper suggest removing the first vertex only, and then recomputing the 00457 // shortest path. Howeve, the paper says the focus is on efficient vertex & edge removal, 00458 // rather than collision checking, so this modification is in the spirit of the paper. 00459 if (!milestonesToRemove.empty()) 00460 { 00461 unsigned long int comp = vertexComponentProperty_[start]; 00462 // Remember the current neighbors. 00463 std::set<Vertex> neighbors; 00464 for (std::set<Vertex>::iterator it = milestonesToRemove.begin() ; it != milestonesToRemove.end() ; ++it) 00465 { 00466 boost::graph_traits<Graph>::adjacency_iterator nbh, last; 00467 for (boost::tie(nbh, last) = boost::adjacent_vertices(*it, g_) ; nbh != last ; ++nbh) 00468 if (milestonesToRemove.find(*nbh) == milestonesToRemove.end()) 00469 neighbors.insert(*nbh); 00470 // Remove vertex from nearest neighbors data structure. 00471 nn_->remove(*it); 00472 // Free vertex state. 00473 si_->freeState(stateProperty_[*it]); 00474 // Remove all edges. 00475 boost::clear_vertex(*it, g_); 00476 // Remove the vertex. 00477 boost::remove_vertex(*it, g_); 00478 } 00479 // Update the connected component ID for neighbors. 00480 for (std::set<Vertex>::iterator it = neighbors.begin() ; it != neighbors.end() ; ++it) 00481 { 00482 if (comp == vertexComponentProperty_[*it]) 00483 { 00484 unsigned long int newComponent = componentCount_++; 00485 componentSize_[newComponent] = 0; 00486 markComponent(*it, newComponent); 00487 } 00488 } 00489 return base::PathPtr(); 00490 } 00491 00492 // start is checked for validity already 00493 states.push_back(stateProperty_[start]); 00494 00495 // Check the edges too, if the vertices were valid. Remove the first invalid edge only. 00496 std::vector<const base::State*>::const_iterator prevState = states.begin(), state = prevState + 1; 00497 Vertex prevVertex = goal, pos = prev[goal]; 00498 do 00499 { 00500 Edge e = boost::lookup_edge(pos, prevVertex, g_).first; 00501 unsigned int &evd = edgeValidityProperty_[e]; 00502 if ((evd & VALIDITY_TRUE) == 0) 00503 { 00504 if (si_->checkMotion(*state, *prevState)) 00505 evd |= VALIDITY_TRUE; 00506 } 00507 if ((evd & VALIDITY_TRUE) == 0) 00508 { 00509 boost::remove_edge(e, g_); 00510 unsigned long int newComponent = componentCount_++; 00511 componentSize_[newComponent] = 0; 00512 markComponent(pos, newComponent); 00513 return base::PathPtr(); 00514 } 00515 prevState = state; 00516 ++state; 00517 prevVertex = pos; 00518 pos = prev[pos]; 00519 } 00520 while (prevVertex != pos); 00521 00522 PathGeometric *p = new PathGeometric(si_); 00523 for (std::vector<const base::State*>::const_reverse_iterator st = states.rbegin(); st != states.rend(); ++st) 00524 p->append(*st); 00525 return base::PathPtr(p); 00526 } 00527 00528 ompl::base::Cost ompl::geometric::LazyPRM::costHeuristic(Vertex u, Vertex v) const 00529 { 00530 return opt_->motionCostHeuristic(stateProperty_[u], stateProperty_[v]); 00531 } 00532 00533 void ompl::geometric::LazyPRM::getPlannerData(base::PlannerData &data) const 00534 { 00535 Planner::getPlannerData(data); 00536 00537 // Explicitly add start and goal states. Tag all states known to be valid as 1. 00538 // Unchecked states are tagged as 0. 00539 for (size_t i = 0; i < startM_.size(); ++i) 00540 data.addStartVertex(base::PlannerDataVertex(stateProperty_[startM_[i]], 1)); 00541 00542 for (size_t i = 0; i < goalM_.size(); ++i) 00543 data.addGoalVertex(base::PlannerDataVertex(stateProperty_[goalM_[i]], 1)); 00544 00545 // Adding edges and all other vertices simultaneously 00546 foreach(const Edge e, boost::edges(g_)) 00547 { 00548 const Vertex v1 = boost::source(e, g_); 00549 const Vertex v2 = boost::target(e, g_); 00550 data.addEdge(base::PlannerDataVertex(stateProperty_[v1]), 00551 base::PlannerDataVertex(stateProperty_[v2])); 00552 00553 // Add the reverse edge, since we're constructing an undirected roadmap 00554 data.addEdge(base::PlannerDataVertex(stateProperty_[v2]), 00555 base::PlannerDataVertex(stateProperty_[v1])); 00556 00557 // Add tags for the newly added vertices 00558 data.tagState(stateProperty_[v1], (vertexValidityProperty_[v1] & VALIDITY_TRUE) == 0 ? 0 : 1); 00559 data.tagState(stateProperty_[v2], (vertexValidityProperty_[v2] & VALIDITY_TRUE) == 0 ? 0 : 1); 00560 } 00561 }