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:

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:

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:

  1. Its declarative approach means the code is maintainable and easily extensible.
  2. 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