algorithms.h
Go to the documentation of this file.
00001 /*********************************************************************
00002 *
00003 * Software License Agreement (BSD License)
00004 *
00005 *  Copyright (c) 2014, ISR University of Coimbra.
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 the ISR University of Coimbra 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: David Portugal (2011-2014), and Luca Iocchi (2014-2016)
00036 *********************************************************************/
00037 
00038 typedef unsigned int uint;
00039 
00040 
00041 typedef struct {
00042   int id, dist, elem_path;
00043   int path[1000];
00044   bool visit;
00045 }s_path;
00046 
00047 typedef struct {
00048   int id, elem_path;
00049   double dist;
00050   int path[1000];
00051   bool visit;
00052 }s_path_mcost;
00053 
00054 typedef struct {
00055   uint current_vertex, next_vertex;
00056   double time_then;
00057   uint num_possible_neighs;
00058   uint id_neighbors [8];
00059   double idleness_old[8];
00060   uint node_count [8];
00061   double entropy;
00062 
00063 }reinforcement_learning;
00064 
00065 
00066 inline long double log2(const long double x);
00067 
00068 uint random (uint current_vertex, vertex *vertex_web);
00069 
00070 uint conscientious_reactive (uint current_vertex, vertex *vertex_web, double *instantaneous_idleness);
00071 
00072 uint heuristic_conscientious_reactive (uint current_vertex, vertex *vertex_web, double *instantaneous_idleness);
00073 
00074 uint greedy_bayesian_strategy (uint current_vertex, vertex *vertex_web, double *instantaneous_idleness, double G1, double G2, double edge_min);
00075 
00076 int count_intention (uint vertex, int *tab_intention, int nr_robots);
00077 
00078 uint state_exchange_bayesian_strategy (uint current_vertex, vertex *vertex_web, double *instantaneous_idleness, int *tab_intention, int nr_robots, double G1, double G2, double edge_min);
00079 
00080 void dijkstra( uint source, uint destination, int *shortest_path, uint &elem_s_path, vertex *vertex_web, uint dimension);
00081 
00082 int is_neigh(uint vertex1, uint vertex2, vertex *vertex_web, uint dimension);
00083 
00084 void dijkstra_mcost( uint source, uint destination, int *shortest_path, uint &elem_s_path, vertex *vertex_web, double new_costs[][8], uint dimension);
00085 
00086 uint heuristic_pathfinder_conscientious_cognitive (uint current_vertex, vertex *vertex_web, double *instantaneous_idleness, uint dimension, uint *path);
00087 
00088 //Check if an element belongs to a table
00089 bool pertence (int elemento, int *tab, int tam_tab);
00090 
00091 int pertence_idx (int elemento, int *tab, int tam_tab);
00092 
00093 bool UHC (vertex *vertex_web, int v1, int *caminho_principal, uint dimension);
00094 
00095 void clear_visited (vertex *vertex_web, uint dimension);
00096 
00097 bool procurar_ciclo (vertex *vertex_web, uint dimension, int *caminho_principal, int &elem_caminho, int &custo_max, int seed);
00098 
00099 int devolve_viz_unicos (vertex *vertex_web, int vertice);
00100 
00101 int longest_path (vertex *vertex_web, int origem, int destino, int *lista_v1v, int i_list, int dimension, int seed, int *caminho_parcial, int &elem_cp);
00102 
00103 bool caminho_apartir_vizinhos_unicos (vertex *vertex_web, int dimension, int *caminho_principal, int &elem_max, int &custo_max, int seed);
00104 
00105 bool verificar_arco_cp (int no_1, int no_2, int *caminho_principal, int elem_cp);
00106 
00107 bool check_visited (vertex *vertex_web, int dimension);
00108 
00109 int devolve_vizinhos_nao_visitados (vertex *vertex_web, int dimension, int vertice);
00110 
00111 bool computar_caminho_de_ida (vertex *vertex_web, int dimension, int *caminho_de_ida, int &elem_c_ida, int *caminho_principal, int elem_cp, int num_arcos);
00112 
00113 int computar_custo_caminho_final (vertex *vertex_web, int *caminho_final, int elem_caminho_final);
00114 
00115 int cyclic (uint dimension, vertex *vertex_web, int *caminho_final);
00116 
00117 void shift_cyclic_path (uint start_vertex, int *caminho_final, int elem_caminho_final);
00118 
00119 uint get_MSP_dimension (const char* msp_file);
00120 
00121 void get_MSP_route (uint *route, uint dimension, const char* msp_file);
00122 
00123 void create_source_and_dest_tables(vertex *vertex_web, uint *source, uint *destination, uint dimension);
00124 
00125 void get_hist_sort(vertex *vertex_web, double *hist_sort, uint dimension);
00126 
00127 int get_hist_idx_from_edge_cost (double *hist_sort, uint size, double edge_cost);
00128 
00129 int get_hist_idx (uint *source, uint *destination, uint source_vertex, uint dest_vertex, uint hist_dimension);
00130 
00131 double get_edge_cost_between (vertex *vertex_web, uint vertex_A, uint vertex_B);
00132 
00133 void load_real_histogram(double *real_histogram, uint size_hist, char* filename);
00134 
00135 void normalize_histogram(double *real_histogram, double *histogram, uint size_hist);
00136 
00137 int pertence_uint_idx (uint elemento, uint *tab, uint tam_tab);
00138 
00139 int get_min(uint *tab, uint tam_tab);
00140 
00141 double get_min_dbl(double *tab, uint tam_tab);
00142 
00143 int get_max(uint *tab, uint tam_tab);
00144 
00145 double get_max_dbl(double *tab, uint tam_tab);
00146 
00147 void write_histogram_to_file (vertex *vertex_web, double *real_histogram, double *histogram, uint *source, uint *destination, uint hist_dimension, uint number, uint robotid);
00148 
00149 void write_reward_evolution(double reward, uint robotid);
00150 
00151 void update_likelihood_old (reinforcement_learning RL, double *real_histogram, double *hist_sort, uint size_hist, vertex *vertex_web);
00152 
00153 void update_likelihood (reinforcement_learning RL, double *real_histogram, uint *source, uint *destination, uint hist_dimension, vertex *vertex_web, int minimum_global_node_count, uint robotid);
00154 
00155 void update_likelihood_new (reinforcement_learning RL, uint *node_count_table, double *inst_idleness, uint dimension, double *real_histogram, uint *source, uint *destination, uint hist_dimension, vertex *vertex_web, uint robotid);
00156 
00157 int learning_algorithm(uint current_vertex, vertex *vertex_web, double *instantaneous_idleness, double *avg_idleness, int *tab_intention, double *histogram, uint *source, uint *destination, uint hist_dimension, int nr_robots, int id_robot, uint *node_count, reinforcement_learning &RL);
00158 
00159 
00160  


patrolling_sim
Author(s):
autogenerated on Mon Oct 2 2017 03:13:50