Attending mind-numbing meetings is not one of them.

Photo by Oskar Yildiz on Unsplash

Waking up in the morning, feeling refreshed after a good night’s sleep, and more importantly, you know what you want to do today.

Starting your day at the office attending 15-minute stand-up, to share progress and issues you and your team faced the previous day. 15 minutes sharp and the stand-up end.

You are clear about the priority of the tickets assigned to you, you work on them in order from the highest to the lowest, but today you will focus on working on one of them.

You start your day, everything…


Step-by-step Algorithm Implementation: from Pseudo-code and Equations to Python Code. In this article, we will implement the Planning Graph and its planner — the GraphPlanner in Python, data structure and search algorithm for AI Planning.

Planning Graph Implementation in Python (Image by Author)

Introduction

Planning Graph was developed to solve the issues in complexity found in the classical AI Planning approaches, a.k.a STRIPS-like planners. There are two main parts that we need to implement:

  • Planning Graph: the Data Structure, and
  • Graph Planner: the Search Algorithm to find us the solution Plan

If you are not familiar with the Planning Graph and want to understand more, check out my post…


Getting Started

Learning the step-by-step implementation of HFSM concepts in Python.

HFSM in Python (Image by Author)

I wanted to use the HFSM (Hierarchical Finite State Machine) in my Pacman AI Agent Implementation to fully understand the concepts and to compare it with the Behavior Tree. In my experience, after reading books and papers of some technical topics, my comprehension of the topics would greatly improve if I implemented them in code.

Pacman AI is written in Python and so I tried searching HFSM implementation on Github, but couldn’t find a good one for my implementation and decided to write one and release it on Github.

In this article, I want to share what I have learned…


Automatically build and update Behavior Trees during run-time.

Automated Planning with Behavior Trees (Image by Author)

Introduction

We have seen how powerful the behavior tree is, in the previous post.

It is hierarchical, modular, and more importantly reactive to changes that happen in the agent’s environment.

It can be used to replace Hierarchical Finite State Machines (HFSMs), to make the systems more scalable and understandable to humans.

However, as you may have noticed behavior trees can become very complex if we want the agent to select between many methods to achieve a goal or a task.

Let’s look at an example.

Transportation System

When we plan a trip to a city in another country, we usually start with a…


Designing and Implementing Behaviors for AI Agents

A Behavior Tree (Image by author)

Introduction — Another way of implementing Acting Engine

In our previous posts, we discussed about Planning and Acting. Both are for planning, one with a Descriptive Model and the other with an Operational Model of actions.

Acting with Operational Model uses Refinement Methods to refine abstract tasks into subtasks or commands that can be executed by Execution Platform. In a rather complex domain where there are multiple methods that we can use to refine a task, this approach excels.

However, for many less complex systems, we only have one/two methods that we can use to refine an abstract task into. One may argue that we don’t need planning…


Using Constraint Satisfaction Problems to solve AI Planning Problems.

Photo by Markus Winkler on Unsplash

Introduction

Just like AI Planning as Satisfiability, we can use an existing technique — Constraint Satisfaction Problems to help us solve AI Planning Problems. This way we can use the existing well-developed algorithms for solving CSPs to solve our AI Planning Problems.

We will first go through the general introduction of CSPs. We then continue to see how to encode AI Planning Problems into CSPs. Finally, we use CSP Backtracking Algorithm to solve our problems. We will prove all these theories by implementing them in Python.

Constraint Satisfaction Problems

From Wikipedia,

CSPs are mathematical questions…


Solving AI Planning Problem using Boolean (Propositional) Satisfiability Problem — another approach to improve expressiveness and complexity in Classical Planning.

Davis-Putnam SAT Solver (Image by Author)

Introduction

This is yet another approach to improve the expressiveness and complexity of the classical planning approaches.

In this technique what we do is convert our classical planning problems representation into a well-known representation called Propositional Satisfiability Problem, also called Boolean Satisfiability Problem, or simply SAT.

If we can convert it to a well-known problem representation, we can use existing algorithms to solve the problems.

If you are not familiar with classical planning approaches, please read the Introduction section in my previous post linked below.

In this post, I’ll explain the concept by going through examples step-by-step.

Propositional Satisfiability Problem (SAT)

SAT is a way…


Using a new search-space, the Planning Graph to improve expressiveness and complexity issues found in Classical Planning approaches.

Planning Graph (Image by Author)

Introduction

The classical approaches to AI Planning use state-space and plan-space to search solution plans to solve planning problems. In the state-space searching, the initial world state goes through several transformations by applying applicable actions until a solution plan is found to reach the goal or the search algorithm terminates and returns failure. We can use the search algorithms such as BFS, DFS, Dijkstra’s, A*, and others.


Learning the details of Hierarchical Finite State Machine (HFSM), how it solves issues found in Finite State Machine (FSM), and how it compares with Behavior Trees.

Pacman HFSMs (Image by Author)

Introduction

Implementing an artificially intelligent agent such as a robot or a character in video games is becoming more complex as they require to have complex behaviors to carry out their tasks in dynamic environments. Today, Finite State Machine (FSM) is still the most used algorithm to model the behaviors of AI Agents.

Despite its weaknesses that have been solved partly by Hierarchical Finite State Machine (HFSM), the fact that it is easy to understand and implement has made it the most commonly used algorithm.

This post will look into the FSM, its advantages and disadvantages, and HFSM which was developed…


Planning actions by simulating the Acting Engine

SeRPE

RAE

In the previous post, we discussed the RAE (Refinement Acting Engine) that plans the actions by refining tasks into executable actions and does that with the observed world state instead of the predicted world state. For the full article, please read here:

One thing that you may have noticed in that approach is the lack of planning in advance.

In some scenarios, planning in advance may give us a more optimal solution to our problem.

By planning, we can explore different courses of action and choose a good solution.

Sequential Refinement Planning Engine

SeRPE is based on RAE and it only supports a single…

Debby Nirwan

Software Engineering Manager who loves reading, writing, and coding.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store