6
\$\begingroup\$

I am implementing the Bellman equation for utilities, in a grid environment as follow. It is an example on Chapter 17 of Artificial Intelligence: A Modern Approach 3rd Edition.

There are some math bended in, I would be extremely appreciate if you can verify the mathematical accuracy of my implementation, but if it takes too much time, any comments on programming technique or data structure is very much welcome. I am impementing using C++, not my most familiar language, so newbie errors aheads.

The problem: Given this grid. An agent (or robot) can move to 4 direction, N, E, W, S.

 |----|----|----|----|
3| ** |    |    | +1 |
 |----|----|----|----|
2|    | x  |    | -1 |
 |----|----|----|----|
1|    |    |    |    |
 |----|----|----|----|
   1    2    3    4 

Each time an agent (**) moves to a cell, it would receive a reward from that cell. The +1 and 1 is the end state, once the agent move to those cell, the game is over. x is an obstacle, which bounces the agent back when being hit.

The agent, however, has the probability to side step (p=0.1).

Sidestep (p=0.1)
↑
xx ----> Intended direction (p=0.8)
↓
Sidestep (p=0.1)

The goal is find a policy that would earn the highest reward. For example, with a reward of -0.04 per cell, optimal policy is

→  →  →  ✗
↑  ✗  ↑  ✗
↑  ←  ↑  ←

Where a reward of 1 would result in this policy

↓  ←  ←  ✗
↓  ✗  ↓  ✗
→  →  ↓  ↓

Basically the agent never wants to enter the end states since life is good.

The extended version of Bellman equation looks like (γ) is the discounting factor

U(1,1)=−0.04+γ max[ 0.8U(1,2)+0.1U(2,1)+0.1U(1,1),               (Up)
                    0.9U (1, 1) + 0.1U (1, 2),                   (Down)
                    0.9U (1, 1) + 0.1U (2, 1),                   (Left)   
                    0.8U (2, 1) + 0.1U (1, 2) + 0.1U (1, 1) ].   (Right)

The problem is pretty similar to https://gym.openai.com/envs/FrozenLake-v0/.

My code is at https://github.com/minhtriet/gridworld, but I still post them here.

try.cpp (Main file)

#include <fstream>
#include <vector>
#include <limits>
#include "Board.cpp"


void read_special_states(std::fstream& fp, std::vector<Point>& states, Board& board) {
    int n_states;
    int temp_x, temp_y;
    fp >> n_states;
    states.resize(n_states);
    for (auto& state : states) {
        fp >> temp_x >> temp_y;
        state.x = temp_x;
        state.y = temp_y;
        board.best_policy[temp_x][temp_y] = Point(0,0);
        board.best_value[temp_x][temp_y] = std::numeric_limits<float>::lowest();
    }
}

void init_board(Board& board, char *filename) {
    std::fstream fp(filename);

    int n_row, n_col;
    fp >> n_row >> n_col;
    board.height = n_row;
    board.width = n_col;

    fp >> board.start_state.x >> board.start_state.y;
    fp >> board.reward;
    board.best_value = std::vector(n_col, std::vector<float>(n_row, board.reward));
    // init to a random value to discourage staying in the same place
    board.best_policy = std::vector(n_col, std::vector<Point>(n_row, Point(0,1)));
    read_special_states(fp, board.end_states, board);
    read_special_states(fp, board.obstacles, board);
    for (auto i : board.end_states) {
        fp >> board.best_value[i.x][i.y];
    }
}


int main(int argc, char *argv[]) {
    Board board;
    init_board(board, argv[1]);
    board.run();
    return 0;
}

Point.h

#include <ostream>

struct Point {
    int x;
    int y;
    public:
        Point();
        Point(int x_, int y_);
        std::ostream operator<<(const Point& p) ;
};

Board.h

#include <vector>
#include <map>
#include <queue>
#include "Point.cpp"

class Board {
    private:
        bool is_inside(const Point& location);
        std::queue<Point> schedule;
    public:
        std::vector<std::vector<float>> best_value;
        std::vector<std::vector<Point>> best_policy;
        int width;
        int height;
        std::vector<Point> direction{Point(1, 0), Point(0, 1),
            Point(-1, 0), Point(0, -1)};
        std::vector<Point> end_states;
        Point start_state;
        std::vector<Point> obstacles;
        float reward;
        float gamma{0.9};
        float move(const Point& current_loc, const Point& direction);
        float move(const Point& current_loc, const Point& direction, float prob);
        const std::vector<float> probs{0.8, 0.1, 0.1};
        void init(const Point& start_state);
        int run();
};

Point.cpp

#include "Point.h"

Point::Point(): x{0}, y{0} {}
Point::Point(int x_, int y_): x{x_}, y{y_} {}
std::ostream &operator<<(std::ostream& os, const Point& p) {
    if (p.x == 1 && p.y == 0) return os << "→";
    if (p.x == -1 && p.y == 0) return os << "←";
    if (p.x == 0 && p.y == -1) return os <<  "↑";
    if (p.x == 0 && p.y == 1) return os << "↓";
    if (p.x == 0 && p.y == 0) return os << "✗";
    return os << "(" << p.x << ";" << p.y << ")";
}

Board.cpp

#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cmath>
#include "Board.h"
#include "util.cpp"


bool Board::is_inside(const Point& location) {
    if ((location.x >= 0) && (location.y >= 0) \
            && (location.x < this->width) && (location.y < this->height))
        return true;
    return false;
}

float Board::move(const Point& current_loc, const Point& direction) {
    float total_reward = 0;
    if (direction.x == 0) {
        total_reward += move(current_loc, Point(-1, 0), this->probs[1]);
        total_reward += move(current_loc, Point(1, 0), this->probs[2]);
    }
    if (direction.y == 0) {
        total_reward += move(current_loc, Point(0, -1), this->probs[1]);
        total_reward += move(current_loc, Point(0, 1), this->probs[2]);
    }
    if (!util::is_in_vector(current_loc + direction, this->end_states)) {
        total_reward += Board::move(current_loc, direction, this->probs[0]);
        total_reward *= gamma;
        total_reward += this->reward;
    } else {
        total_reward *= gamma;
        total_reward += Board::move(current_loc, direction, this->probs[0]);
    }
    return total_reward;
}

float Board::move(const Point& current_loc, const Point& direction,
        float prob) {
    Point new_loc = current_loc + direction;
    // edge cases
    if (util::is_in_vector(new_loc, this->obstacles) || !is_inside(new_loc)) {
        return prob * best_value[current_loc.x][current_loc.y];
    }
    if (util::is_in_vector(new_loc, this->end_states)) {
        return prob * best_value[new_loc.x][new_loc.y];
    }
    // end of edges cases
    return prob * this->best_value[new_loc.x][new_loc.y];
}

int Board::run() {
    for (int i = 0; i < 10; i++) {
        this->schedule.push(start_state);
        std::vector<Point> visited;
        while (this->schedule.size() > 0) {
            Point p = schedule.front();
            this->schedule.pop();
            visited.insert(visited.begin(), p);
            float result, best_result = std::numeric_limits<float>::lowest();
            Point best_direction;
            for (auto direction : direction) {
                Point new_loc = p + direction;
                if (this->is_inside(new_loc)) {
                    if (!util::is_in_vector(new_loc, visited)
                            && (!util::is_in_vector(new_loc, obstacles))
                            && (!util::is_in_vector(new_loc, end_states))) {
                        schedule.push(new_loc);
                    }
                }
                result = move(p, direction);
                if (result > best_result) {
                    best_result = result;
                    best_direction = direction;
                }
            }
            best_value[p.x][p.y] = best_result;
            best_policy[p.x][p.y] = best_direction;
        }
        util::print<float>(best_value);
        util::print<Point>(best_policy);
    }
    return 0;
}

util.cpp

#include<vector>
#include <iostream>
#include <iomanip>
#include <type_traits>
#include <limits>

namespace util {

    template <typename T>
        bool is_in_vector(const T& location, const std::vector<T>& to_check) {
            if (std::find(to_check.begin(), to_check.end(), location)
                    != to_check.end()) {
                return true;
            }
            return false;
        }

    template <typename T>
        void print(const std::vector<std::vector<T>>& matrix) {
            std::cout << std::setprecision(3) << std::fixed;
            for (int j=0; j < matrix[0].size(); j++) {
                for (int i=0; i < matrix.size(); i++) {
                    if (matrix[i][j] == std::numeric_limits<T>::lowest()) {
                        std::cout << "✗  ";
                        continue;
                    }
                    std::cout << matrix[i][j] << "  ";
                }
                std::cout << "\n";
            }
        }
}

Point operator+(const Point& p0, const Point& p1) {
    return Point(p1.x + p0.x, p1.y + p0.y);
}
bool operator==(const Point& p0, const Point& p1) {
    return (p1.x == p0.x) && (p1.y == p0.y);
}
bool operator<(const Point& p0, const Point& p1) {
    return (p1.x < p0.x) || (p1.y < p0.y);
}

EDIT: The code compiles and give out correct result for the policy. For the values (or return) calculation, it is consistency 0.05 higher than the expected value across the board (and I am not sure if I should investigate on this).

\$\endgroup\$
  • 1
    \$\begingroup\$ Does this actually compile and run for you, and provide expected output? Also please specify what operating system and compiler you are using. \$\endgroup\$ – pacmaninbw Jul 17 at 23:27
  • \$\begingroup\$ Hi @pacmaninbw please see my edit at the end \$\endgroup\$ – Minh Triet Jul 18 at 4:47
3
\$\begingroup\$

Program and File Structure
As a general rule C++ source files (.cpp) are not included in other C++ source files, each .cpp file is compiled separately and the resulting object files are linked together by the linker. The benefits of this are that the entire program does not need to be rebuilt when a .cpp file is modified, just the module that was modified and then the program is re-linked. This allows bug fixes and feature requests to be implemented without rather long build times. If the program is implemented in shared libraries it means just a single library may need to be updated for bug fixes to be delivered to users.

In some cases very simple classes may be implemented using only a header file.

One of the problems with including source files in other source files is that it can lead to multiple definitions of objects or functions at link time. An example would be using the util.cpp in multiple other source files.

A second possible problem with including source files in other source files is that the compile time for the final source file will increase.

In C++ classes are generally implemented as a header file (.h or .hpp) and a C++ source file pair. The structure and public interface of the class are in the header file and in most cases the internal implementation of the class is in the C++ source file. Public interfaces are expected to not change often but internal implementation can change as often as necessary.

In try.cpp board.cpp is included, this ends up including point.cpp and util.cpp, the problem with this is that the main() function only needs to know about the Board class, it does not need to know about the Point struct or the items in util.cpp.

Rather than using compile.sh to build the project it might be better to use an Integrated Development Environment (IDE) such as Eclipse CDT or Visual Studio. In both cases the development environments create the build process for the program as well as providing a programming and debugging interface. Eclipse is an open source project and can be downloaded for free, there is a free version of Visual Studio as well. If you are developing on Linux Eclipse is part of the development options. Programming and debugging using an IDE is much easier, the code is scanned as it is entered which reduces compile time errors. In most IDE's you can select the C++ standard you want to work with (C+=11, C++14, C++17, ...).

Class and Object Initialization
In Board.h there is a public method called void init(const Point& start_state);. This function is not defined or implemented anywhere which may cause linking errors in some build environments. In try.cpp there is instead a function called void init_board(Board& board, char *filename). Classes should handle their own initialization in their constructors. Class constructors can use sub functions as necessary. A function such as init_board() forces the knowledge of internals of the board class on outside structures and forces members of the Board class to be declared public where the might be better declared as either protected or private. examples of members of Board that should be private or protected are std::vector<std::vector<float>> best_value; and std::vector<std::vector<Point>> best_policy;. The function void read_special_states(std::fstream& fp, std::vector<Point>& states, Board& board) in try.cpp might better be a member function of the Board class. This would reduce the number of parameters to the function and might be called by the Board constructor. Note there can be multiple Board constructors, one that takes a file name and one that doesn't. A safer way to do this might be to create the file pointer in main() test to see that the file exists and then pass the file pointer to the Board constructor.

Error Checking, Handling and Reporting
The main() program assumes that there is at least one command line argument, this is not safe there should be a function to parse the command line called by main(). In the function init_board() there is no test that there is a file or that it can be opened, this is also not a safe practice. In either of the functions the program can fail without the user knowing because of a simple user error, either not entering a file name or entering the wrong file name. A good practice is to check user input and provide meaningful error messages when user input is incorrect.

The Use of this to Access Members
In Board.cpp the this pointer is used many times, unlike PHP and some other languages in C++ there is generally no reason to use the this pointer. When an object is compiled in a .cpp file the compiler will first look for local symbols within the class.

Code Complexity
In the util.cpp file the function is_in_vector() could be simplified to:

template <typename T>
bool is_in_vector(const T& location, const std::vector<T>& to_check) {
    return (std::find(to_check.begin(), to_check.end(), location) != to_check.end());
}

Public Versus Private in struct
In C++ in a struct all fields are public by default. In Point.h there is no reason to have public for the members Point(), Point(int x_, int y_) and std::ostream operator<<(const Point& p). If the members x and y should be private, you can either specify that or make the struct into a class. Making Point a class might simplify the code in std::ostream operator<<(const Point& p) since it would no longer be necessary to add p as an argument. It might be better to move the Point operators in util.cpp into either Point.h or Point.cpp.

Magic Number
It is not clear what the numeric value 10 represents in the for loop in Board::run(). It might be better to create a symbolic constant somewhere in the program, or for Board to have a member size_t variable that is used in that loop.

Unnecessary Include Files
Board.cpp includes cassert and cmath, but they are not used within the file.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.