STRIPS AI Planning in E-Shop Checkout Flows

The demo below simulates how an AI planning algorithm would dynamically guide a shopper through a checkout flow according to different facts about the shopper and their order.

Note: To show how the planning algorithm would react to different situations, you can configure things here that no e-shop cart would know in advance. In the real world, the planner would execute every time the user completes a step (e.g. fills in part of a form) and would only present the first step of the rest of the path.

The problem

Checkout flows are hard to get right. Even when buying from big e-commerce players — who invest lots of time and resources into optimizing their websites — shoppers are subject to following issues:

Filling in information that has nothing to do with their order (for example, shipping address for digital goods).
Being asked questions that make no sense given their previous answers (for example, US state for shoppers from other countries).
Manually repeating information that has already been given.
Filling in information that could have easily been predicted from earlier inputs (for example, city name after filling in ZIP code).
- On the other hand, having to go with the default when it doesn't make sense (for example, no way to enter different city name than what was, maybe, incorrectly guessed) is also a problem.
Having to go through much of the checkout process to find out that their order cannot be completed (for example, buying an item that is not available outside US).

It is clear that no single, monolithic checkout flow can address all these issues. On the other hand, dynamically constructing the flow via naive if-else logic can quickly lead to unwieldy code and bugs (read: combinatorial explosion).

STRIPS

STRIPS (Stanford Research Institute Problem Solver) is an automated planner originally developed by Richard Fikes and Nils Nilsson in 1971.

With STRIPS, you have the following:

An initial state (in our example: we know nothing about the shopper).
A desired state (in our example: we know everything we need to know about the shopper to be able to finish their order)
A set of actions that change state (in our example, things like: "ask the user about their name")

Given these things, the algorithm can construct a plan by simple path-finding.

This particular example uses a subset of STRIPS called Goal Oriented Action Planning (GOAP) which is popular in games AI programming. Jeff Orkin's 3 States and a Plan: The AI of F.E.A.R. (PDF) is a great explanation of GOAP (and, by extension, STRIPS).

Applying STRIPS to checkout flows

When applied to the problem at hand, the beauty of STRIPS (and GOAP) is twofold:

Its declarative approach means the code is maintainable and easily extensible.
The search algorithm will always find the optimal flow, or fail fast.

For example, if the e-shop starts selling items that need yet another additional information (such as VAT ID), developers only need to implement one additional action (with a correct prerequisite and consequence). If that additional information can be (partly) pre-filled with help of some other information (such as EU VAT ID being pre-filled with country code), the algorithm itself will make sure it asks its questions in the correct order.

Caveats

Caveats that apply to declarative programming in general apply here, too. Declarative programming is not the proverbial silver bullet. Part of the complexity that gets abstracted (for example, the if-else spaghetti code) is gained back through other means (for example, the need to fine-tune the prerequisites so that the flow seems "natural"). Also, declarative programming algorithms tend to be slower than optimized imperative algorithms.

This particular implementation is experimental and untested in the real world. It is presented here as an inspiration.

Code

This demo is implemented in Dart and runs solely in the browser. The GOAP algorithm itself is a Dart package available on github.

The actual code that plans the checkout flow looks like this:

var planner = new EshopCartPlanner();
// set current state
var solution = await planner.plan();
// do stuff with solution

Here's a snippet that declares some of the actions you can see in the demo. All actions have a consequence (the first, unnamed closure) and most have a prerequisite.

actions = <EshopCartModule>[
  new EshopCartModule("Name", (EshopCartState s) {
    s.haveName = true;
  }),

  new EshopCartModule("Country", (EshopCartState s) {
    s.haveCountry = true;
  },
      prerequisite: (EshopCartState s) => s.needsShippingAddress),

  new EshopCartModule("Zip Code", (EshopCartState s) {
    s.haveZipcode = true;
  }, prerequisite: (EshopCartState s) => s.haveCountry),

  new EshopCartModule("US State", (EshopCartState s) {
    s.haveUsState = true;
  }, prerequisite: (EshopCartState s) => s.haveCountry && s.isUs),

  new EshopCartModule("City", (EshopCartState s) {
    s.haveCity = true;
  }, prerequisite: (EshopCartState s) => s.haveStreet),

  new EshopCartModule("Confirm City (guessed from ZIP)",
      (EshopCartState s) {
    s.haveCity = true;
  },
      prerequisite: (EshopCartState s) => s.haveZipcode && s.haveStreet,
      cost: 0.1),

  // ...

  new EshopCartModule("Log In", (EshopCartState s) {
    if (!userWillLogin) return;
    s.loggedIn = true;
    s.haveName = true;
    s.haveCountry = true;
    s.haveZipcode = true;
    s.haveUsState = true;
    s.haveCity = true;
    s.haveStreet = true;
    s.haveInvoiceAddress = true;
  }),

  new EshopCartModule("Confirm Price", (EshopCartState s) {
    s.priceConfirmed = true;
  },
      prerequisite: (EshopCartState s) => !s.isFree && s.havePaymentInfo),

  // ...

  new EshopCartModule("Will Not Ship (non-US)", (EshopCartState s) {
    s.orderFinished = true;
  },
      prerequisite: (EshopCartState s) =>
          (!s.isUs && s.shipsToUsOnly && s.haveCountry),
      cost: 0.5)
];

Hope you found this inspirational or at least mildly entertaining. Please comment on the original Google+ post.

— Filip Hráček
filip.hracek@gmail.com

Setup

Customer

Order