ShortestPathFasterAlgorithm.h

Go to the documentation of this file.

/**
 * This file is part of ArmarX.
 *
 * ArmarX is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * ArmarX is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 *
 * @author     Fabian Reister ( fabian dot reister at kit dot edu )
 * @date       2022
 * @copyright  http://www.gnu.org/licenses/gpl-2.0.txt
 *             GNU General Public License
 */
 
#pragma once
 
#include <optional>
#include <vector>
 
#include <Eigen/Core>
 
#include <armarx/navigation/algorithms/Costmap.h>
 
namespace armarx::navigation::algorithms::spfa
{
 
    class ShortestPathFasterAlgorithm
    {
    public:
        struct Parameters
        {
            bool obstacleDistanceCosts = true;
            // float obstacleMaxDistance = 1000.F;
 
            // float obstacleDistanceWeight = 1.3F;
            float obstacleCostExponent = 4.F;
 
            ///  For ARMAR-7 the following was tested:
            float obstacleMaxDistance = 1500.F;
            float obstacleDistanceWeight = 6.F;
        };
 
        ShortestPathFasterAlgorithm(const Costmap& costmap, const Parameters& params);
 
        struct Result
        {
            Eigen::MatrixXf distances;
            std::vector<std::vector<Eigen::Vector2i>> parents;
 
            // if 0, this cell is not reachable
            using Mask = Eigen::Matrix<bool, Eigen::Dynamic, Eigen::Dynamic>;
 
            Mask reachable;
        };
 
        struct PlanningResult
        {
            std::vector<Eigen::Vector2f> path;
 
            bool success;
 
            operator bool() const noexcept
            {
                return success;
            }
        };
 
        struct ClosestReachableResult
        {
            Eigen::Vector2f position;
            Eigen::Vector2i gridIndex;
            float euclideanDistanceToGoal;
        };
 
        PlanningResult plan(const Eigen::Vector2f& start,
                            const Eigen::Vector2f& goal,
                            bool checkStartForCollision = true) const;
 
        // this function can be used to create multiple paths from the same starting location
        // without having to run the spfa planner multiple times
        PlanningResult constructPath(const Eigen::Vector2f& start,
                                     const std::vector<std::vector<Eigen::Vector2i>>& spfaParents,
                                     const Eigen::Vector2f& goal) const;
 
        Result spfa(const Eigen::Vector2f& start, bool checkStartForCollision = true) const;
 
        // protected:
        /**
         * @brief Implementation highly inspired by github.com:jimmyyhwu/spatial-action-maps
         * 
         * @param input_map 
         * @param source 
         * @return Result 
         */
        Result spfa(const Eigen::MatrixXf& inputMap,
                    const Eigen::Vector2i& source,
                    bool checkStartForCollision = true) const;
 
 
    private:
        const Costmap costmap;
 
        const Parameters params;
    };
 
    std::optional<ShortestPathFasterAlgorithm::ClosestReachableResult>
    findClosestReachablePosition(const ShortestPathFasterAlgorithm::Result& spfaResult,
                                 const Eigen::Vector2f& goal,
                                 const Costmap& costmap);
 
} // namespace armarx::navigation::algorithms::spfa