Introduction

In the problem Decode Ways, we are given sequences of numbers that can correspond to strings. The challenge for today is for us to figure out how many strings possible. I’ll include the screenshot explaining the problem

For this problem, I’ll break down what our algorithmic approach actually is and why it makes sense. Then I’ll be giving some pseudo-code and inductively proving the correctness of that code. First, let’s get into our algorithm technique:

Problem Concepts

What is Dynamic Programming (DP)?

In its essence, Dynamic Programming is the memoization of recursion. DP can also be called “smarter brute force”. The identifying trait of DP is that it tries every possible input, but in a smart way that allows is to reuse previous calculations (without doing them again). Despite it’s reputation as the bad boy of algorithms due to the general fear of the approach, it’s one of the most applicable techniques to actual everyday code.

What is Bottom-Up DP?

In contrast to top-down approach of DP, where we store the past calls of our recursive function (meaning you start with the original problem to answer, and dive down to the base case), bottom-up goes … from the bottom upwards. This approach usually entails figuring out how our algorithm will respond to the very smallest of inputs and then builds up the answer to every sub-problem until we get our final answer.

You can imagine Dynamic Programming like solving a Crossword puzzle. Of course it’s possible to fill in the entire board at once, but realistically you take the entire board word-by-word, cell-by-cell. Each cell in this analogy is a sub-problem, and by solving the sub-problems you eventually get the answer to the entire puzzle.

Inductive Proof

Now let’s get into what matters! I’ll introduce our pseudocode at a high level, and from there we’ll start to break down why for each case.

PseudoCode

function decodeWays(string s):
  n = s.length
  dp= array of size n intialized to 0
  dp[1]= 1 if s[1] != “0”
  if (dp[1] == 0) return 0
  dp[2] = 1 + (1 if s[1] != “0”, else 0) if “10” <= s[1..2] <= “26” 
                            else  (1 if s[1] != “0”, else 0)
  for i in 3…n:
    if s[i] != “0”:
      dp[i] += dp[i-1]
    if “10” <= s[i-1…i] <= “26”: 
      dp[i] += dp[i-2]
  Return dp[n]

Inductive Hypothesis: For any n-size string of integers, our algorithm can decode the total number of strings that can be successfully deciphered

Base Case:

Here we want to say that at the very base steps, our algorithm can successfully solve the very smallest steps

i=1: if this is the case, there are 10 possible values in this index, 0–9. Of these values, the only one that is impossible to make a letter from is 0 (as we saw with the “06”, we can’t translate this to F because 0 simply isn’t translatable to a letter by definition). Thus in our dp array, we can only make a letter if the number in the string is above 0. I’ll give examples below:

• ‘0’ -> nothing, no string can be possibly created (no string starts with 0). Thus 0 strings can be created from this.
• ‘1’ -> A. 1 string can be created, so return 1.
• ‘2’ -> B ……
• ‘9’ -> I. 1 string can be created, so return 1.

As you can see, we’ve mapped all possible outputs from this starting point in 3rd and 4th line function, so we handle this case properly.

i=2: in this case, we can either have two options for the string length. As we learned in the i=1 case, we can’t start a number with 0 as no string maps to it, thus our value must be at least 10.

Now consider all values from 10–26: we have two possible ways to decode for almost every values (e.g. “26” can be decoded as “B, F” or simply “Z”), with the only exception being 10 or 20 (only decoded string is “J” because I can’t convert “0” to a standalone character). For this reason, we can see in line 5 of our code, we can either get 1 or 2 decoded strings based on the number if our string falls under this category.

What about even larger numbers? As we go from 27–99, there is only one possible case here: neither number is 0. Of course we know that ‘03’ can’t be decoded because of the first ‘0’ but also consider ‘30’ — the same problem arises, what number starts with 0? There is none, and so we also have to return 0 if this is the case. Otherwise, we’re simply splitting our 2-string into 2 different letters (e.g. ‘33’ will always be decoded as “CC”, there is no 33rd letter to pose as an alternative way to decode). Looking back at the pseudo-code here, what we notice in line 6 is that if our value is above 26, we just have to check that our second digit isn’t 0, and thus give our single way to decode the letters. Our pseudo-code is correctly dealing with the problem appropriately.

That means for any variation of our base cases, our algorithm will return the correct answer to our decode-ways problem.

Inductive Step:

Great! Now that we know our base of our induction is solid, let’s start to test the actual inductive step. If we assume that our algorithm is correctly measuring how many possible ways can we decode our string s for all values less than n, where n is at least 3 (or else we’d be proving a base case — we already did that), what happens when we decode the n’th digit?

Let’s break this down by possible cases it can fall into:

• If s[n] isn’t 0, then we know that s[n] can be a decoded letter on it’s own! This means that for every string that was possibly decoded from s[1…n], we can now add decoded s[n] and it’ll still be correct. This is why in line 9 of the code, we simply add all results from dp[n-1] into our answer if this is the case.
• Otherwise, let’s think about if the string from s[n-1..n] falls in the range of 10..26. If this is the case, it means that whatever could be decoded from s[1..n-2] can just have the decoded string of s[n-1…n] added onto the end. Now, before we jump back to the base case proof and think about the fact that there are 2 ways to decode most numbers from 10–26, remember that we already included that in our previous step. This time, all we simply do is add all the possible decodings that occurred up to n-2 to our current tracker. This is exactly what we do in line 11 of our code.

This means that whatever the value we get at s[n], we can infact calculate how many possible ways to decode the string with our algorithm. Take a few moments to walk through this with strings of your choice and see the magic. Some examples I’d try are “226”, “301”, and “1201234”

Inductively, for any string of numbers s, we can decode the number of possible ways this string with our algorithm

Runtime + Space

Runtime: O(N)

The reasoning for this is fairly simple: We store the amount of previously decoded strings for each digit leading up to n. By doing this, each step of our for-loop only needs a constant amount of time to run. This leads us to our O(N) time stamp.

Space Complexity: O(1)

You might be thinking: Wait a minute, we just said we’d have to store every value in the DP array? You are correct, I definitely did just say that, but a core step of this problem is realizing you only need to look 2 steps behind each index you’re trying to calculate. So rather than a DP array of size n, we could just fine with one of size 2. It’ll make more intuitive sense with my python code below:

class Solution:
    def numDecodings(self, s: str) -> int:
        """
        Recurrence relation:
        dp[i] = dp[i-1] +   (if l != 0, because every solution )
                dp[i-2] +   (if dp[i-2: i-1] <= "26" and s[i-1] != 0 because 
                            this means s[i-1:i] can be number on it's own)

        Runtime: O(N), have to iterate through every value

        Space: O(1), we don't need to store anything extra
        """
        dp = [None for i in range(2)]
        dp[0] = 0 if s[0] == "0" else 1
        if len(s) == 1 or dp[0] == 0: 
            return dp[0]
        dp[1] = dp[0] + int(s[1] != "0") if "1" <= s[:2] <= "26" else int(s[1] != "0")
       
        for i in range(2, len(s)):
            # dp[i] = dp[i-1] + dp[i-2]
            # ans = dp[i], dp[1] = dp[i-1], dp[0] = dp[i-2]
            ans = 0
            if s[i] != "0": # and "1" <= s[i-2:i] <= "26":
                ans += dp[1] # this can be added to all solutions from i-1
            if "10" <= s[i-1:i+1] <= "26":
                ans += dp[0] # this number can be added onto all previous solutions from i-2
            
            # fix stuff for next step
            dp[0] = dp[1]
            dp[1] = ans

        return dp[1]

When the phrase “social robotics” come to mind, lots of us have a humanoid image in mind: maybe C3-PO, maybe sky-net backed terminators (if you’re quite the cynic). Despite this humanoid image, as college students, we interact with social robotics almost every time we step outside. Here at Purdue we have “starship” robots that deliver food and groceries to students, taking all the same routes on the sidewalk and crosswalk as students. Just like students, roboticists in this area have to ask questions like “how do these robots know to avoid hitting people, and how do they deliver goods while dealing with obstacles and oncoming traffic?”

Beyond just the delivery of goods and the roads, it is natural to wonder how robots will learn to navigate social settings like classrooms, offices, and homes. How will robots begin to learn how to gauge emotions and where people are walking, and give them their appropriate personal space? These are questions answered in the paper we will be going over today, EWareNet by Narayanan et. al.

At a high level, the paper creates robots that are emotionally aware of how people are feeling and create paths that respect their personal space and where they are headed. The paper is not the first to introduce this concept of robotic awareness of humans and traveling alongside them (just think about all the self-driving cars in development), the new approach these researchers took allowed them to beat the State-Of-The-Art algorithms without investing in extremely expensive hardware. This means that this research can be applied to everyday robots, advancing tech everywhere.

Technical Details

What are ANNs?

Artificial Neural Networks are a subset of machine learning whose structure is inspired by the brain. ANN’s have 3 types important layers: input, hidden, and output: each layer processes information from the previous layer and feeds the new information forward into the next layer.

The core ingredient of ANN’s is the neuron, also called the perceptron. Each of the neurons processes and transmits information, allowing the network to learn how to make intelligent decisions.

The computation of each neuron is simply the multiplication of the input (1 or 0) of a feature and its weight. After summing these values, we simply check if this result exceeds our threshold: we output 1 if it does, and 0 otherwise. An example of this can be seen below:

This paper uses multiple different types of ANN’s, including Convolutional Neural Networks (CNN) and Transformers.

Convolutional Neural Networks (CNN’s):

Convolutional Neural Networks are ANN’s that operate on visual data and are the backbone of modern AI and Computer Vision. You can understand CNN’s as scanning over images multiple times and figuring out which features contribute most to an output. Consider an example where you had to figure out whether the animal in the picture is a cat or a dog: features like triangular ears and whiskers may be highly characteristic of cats, and long tongues and floppy ears may be a telltale sign of dogs.

Transformers

Unlike the rest of the ANN’s introduced today, transformers are a relatively new architecture. Much of the ANN’s we see in use were developed decades in the past, the reason for their resurgence comes mainly from the rapid development of computational power and data resources [d2l].

Functionally, Transformers are a type of neural network that are used to process data that occurs in a sequence — like a sentence, or steps in someone’s stride. Transformers work based on the principle of attention. Before I explain what self-attention is and how it works, let me explain how transformers operate on the principle: imagine that you have a sentence in Spanish that you want to translate into English, and each word in the sentence is assigned attention based on its importance. Taking this in, the final output of our transformer simply just has a probability assigned over every word in English — we simply are just picking the most likely word based on what has come before (probabilities will change each time we choose a word).

Self-attention can be thought of as a way to weigh the importance of different elements in a sequence. Imagine you are trying to summarize a physics textbook. The self-attention mechanism would assign a weight to each sentence in the book, based on how important it is to understand the overall meaning of the book. When we learn from these textbooks, we remember certain formulas, principles, and theorems because they represent the core of the knowledge of the textbook — these are the ‘sentences’ that would have the largest assigned weight from the self-attention mechanism.

What is RL?

Reinforcement Learning (RL) is a learning paradigm that learns how to optimally take steps of sequential decisions. RL aims to mimic how we as humans learn: specifically, RL learns which actions to take at any point in time that leads it to its goal (aka the highest reward). Let’s break down the components of RL with analogies to Mario Brothers:

• State space (also called observational space): This describes all available info and features of the environment that we can use to make a decision. In Mario, this would include all of the possible occurrences that could happen at a position (enemy, pit to doom, red mushroom, etc.)
• Action space: Decisions you can take in each state of the system. In Mario, this means left, right, jump, or crouch.
• Reward Signal: This signals the performance of the current action, which is taking from our current state into the next state, which leads us to always consider the path that is giving the highest rewards (e.g. on a flat course in Mario Bros, going right towards the flag will always have a higher reward than going left). Discounted rewards are an approach that forces RL algorithms to optimize their trajectory towards the path (i.e. if Mario has to take 200 states to get to the flag compared to 10, the discounted reward signal should obviously reward the actions of the latter).

High-Level Overview

As with all research papers, there are multiple components that come together to make this whole thing novel. Here we are breaking down each of the parts and the fundamental questions they answer for our robotic friend.

Human Pose Extraction: “Where are the people, and what’s their body language like?

This is the backbone of our entire AI pipeline. Although not as direct of a factor as emotions or path trajectory, these factors are usually very heavily influenced by body language and how we position ourselves. We’ll explore this further in the next few points. This was achieved by using a CNN trained off images of people and their skeletal poses.

Human intent prediction: “Where is this person going?”

In each of the robots we’ve seen, an essential feature of these robots is that they never run into or interrupt a human on their path. Internally, robots accomplish this by predicting trajectories of where people are heading based off their past few strides. While this may seem dramatic, people do the exact same thing when crossing the street: when we’re walking on the left side of the sidewalk and someone is running on the right side of the walk, we tend to assume they’ll stay on that side. This understanding of predicting paths was accomplished using a transformer-based Neural Network, which was trained off series-based data of a person’s strides, and then the subsequent trajectory that resulted from that stride.

Proxemic Constraints Modeling: in a phrase, just think “personal space.”

This part of the paper was aimed at being able to guess how people are feeling based entirely on their body language and facial expressions. As humans, we intuitively know that someone’s personal space is usually based on how they feel, and interrupting anyone’s personal space changes their mood (usually for the worst). Our AI needs to know how people are feeling in order to move without stepping into their personal space, and also understand that if they must get close and personal, what are the consequences of their actions? Here, AI is a CNN that took in inputs of people and their body language (remember pose estimation?) and then outputs predictions of their emotions and proxemic constraints (personal space).

This part is trained primarily by a CNN that inputs images of people and outputs predictions of emotions and proxemic constraints (their personal space).

Intent-Aware Navigation: I have all this information, now what?

This brings all the components together. This part of the experiment sets up an RL-environment that factors in the paths people are taking, their emotions, and how the next action of the robot will take will affect these constraints. We now have pretty much all of the setup for the RL game from the previous points, let’s just match them and see how our robot will optimize:

• State space: This would be all of the information the robot can take in before making its next move. Information like where people are, where they are going, and how they are feeling (and consequently, what is their personal space) are all factors our robot needs in order to take its next action.
• Action space: Most intuitive of the three: where is our robot going? The robot has options to move in any direction or sit still, just like any other person walking also has.
• Reward Signal: rewards for the robot are dependent on how people are feeling. There are things that are obvious to make rewards, like the robot moving closer to its destination, not invading personal space, or interrupting people walking. There are also features that the paper adds in order to support a more cohesive environment, an example of this is negatively rewarding the robot for jittery movements, as that will likely confuse everyone around the robot.

By optimizing for our game, we get an AI-powered bot that moves around in its room from the beginning to the destination that minimizes the time to arrive as well while respecting personal space, smooth routes, and where people are headed. Now let’s see how it performs :^).

Analysis and Takeaways

With all this experimental design, it is imperative we also look at our results. Since the novel parts of this paper deal with how to predict the trajectories of others as well as the performance of an RL-controlled robot, those are the results we’ll discuss, as well as the dataset it operates on.

Trajectory Projection. Using a dataset of 3.6 Million photos of people posing, EWareNet was shown to beat many of the top trajectory prediction networks, while significantly lowering the waiting time for prediction on each. In the paper, they credit the utilization of the Emotional Predictor network — the CNN we discussed earlier — in order to add to the trajectory prediction.

When comparing the RL policy of EwareNet with other State of the Art systems, we see that there is a major reduction in the amount of personal space robots invading. In comparison with the rest of SOTA, EWareNet performs with approximately half the personal space intrusion as its counterparts.

Takeaways

• We introduce a novel approach to guessing the trajectory of humans using transformers based on previous cycles of their footsteps.
• Based on these trajectories, we create a planning algorithm based on reinforcement learning in order to find optimal ways for the robot to reach its end destination with minimum disturbance to human counterparts.
• We also begin to guess how much space they need based off of our (perceived) understanding of how they feel.

Sources:

1. EWareNet — https://arxiv.org/pdf/2011.09438.pdf
2. Emotional Learning for Robotics Settings — https://openaccess.thecvf.com/content_CVPRW_2019/papers/MMLV/Bera_The_Emotionally_Intelligent_Robot_Improving_Socially-aware_Human_Prediction_in_Crowded_CVPRW_2019_paper.pdf
3. transformers explained — dhttps://www.youtube.com/watch?v=4Bdc55j80l8
4. Transformer explanation (and just general great AI utility) — https://d2l.ai/chapter_attention-mechanisms-and-transformers/index.html
5. IBM tutorials, very useful for some quick definitions in AI and SWE — https://developer.ibm.com/learningpaths/get-started-automated-ai-for-decision-making-api/what-is-automated-ai-for-decision-making/

Robotics in Real Life: What makes robots maneuverable in social environments? was originally published in MLPurdue on Medium, where people are continuing the conversation by highlighting and responding to this story.

Today we’re going to be breaking down a popular Blind-75 problem with the Divide-and-Conquer approach, and Rigorously prove the correctness of our code.

This article will cover a few things: problem description, Divide and Conquer overview, pseudocode and its proof (as well as a runtime proof).

The Problem:

Description: Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Visual Example is given below

We know that for each tree, the left and right subtrees each have inorder and preorder traversals, and ideally with those two traversals the subtrees could also be constructed themselves. This condition should apply recursively until the subtrees we are looking at don’t have children at all!

This sort of recursive design, where each subproblem has the same setup as the original problem, is a tell-tale sign of a Divide and Conquer solution being feasible. But how do we design algorithms with Divide and Conquer in mind?

Divide and Conquer: What is it?

The name is pretty accurate to what we’re doing, with DnC algorithms we are:

1. Divide: Finding a way to split our problem into (roughly same-sized subproblems that deal with the same issue as the original problem
2. Conquer: We assume our subproblems (my professor calls them “children”) return correct answers, unless our input is very small (called base case). If our subproblem is small, we instead solve it directly.
3. Merge: With our subproblems solved correctly, what we can now do is combine our correct subproblems together in order to solve our current problem.

Code wise, this translates pretty easy, I like to include an example form Abdul Bari’s DnC video:

Now with the problem and design out of the way, let’s get into the meat and potatoes:

PseudoCode

BuildTree(preorder, inorder):

1. If (preorder or inorder is empty): return None
2. root = TreeNode with node value of preorder[0]
3. Idx = index of root’s value in inorder array
4. leftIn, rightIn = inorder[0…idx-1], inorder[idx+1,…n-1]
5. leftPre, rightPre = pre-order[1…idx], inorder[idx+1,…n-1]
6. root.left = buildTree(leftIn, leftPre)
7. root.right = buildtree(rightIn, rightPre)
8. Return root

Proof of Code

Inductive Hypothesis: Given the preorder and inorder traversal of any size-n tree, we are able to construct a binary tree that matches both the pre-order and in-order traversal of said tree.

Base Case (small input): for a size 0 tree, both the pre-order and in-order traversal of this tree will be empty arrays, specifically ‘None’ in our code (line 1). If this is the case, we should return an empty tree, which we do in line 1 of our pseudocode.

Let’s assume that for any value j, where 0<= j< n, our inductive hypothesis works. What happens if the preorder and inorder arrays (and consequently, the tree) is of size n?

With the preorder and inorder tree, we know by structure of preorder array that the root of the n-size tree is the first element of the array (line 2). Intuitively, this is because preorder array visits the tree in Node-Left-Right, so the first element in the preorder array is a node that isn’t the left or right child of any other node (i.e. ‘the root’).

With this in mind, we can now find the index of root in the in-order tree, call it ‘idx’ (line 3).

Because inorder travels the tree in “Left-Node-Right” order, everything to the left of ‘idx’ in the inorder array is to the left of root (in the left subtree), and everything to the right of ‘idx’ in the inorder array is to the right of the root (in the right subtree), done in line 4 of the proof.

We know this splitting is correct because of the fact that if any subtree has a incorrect subtree inorder traversal, then the whole inorder for the n-size array is incorrect (just draw it out with the example). These are isolated as the inorder traversals of the left and right subtree.

As we learned in the previous paragraph, ‘idx’ tells us how large the left and right subtree of the overall tree is: this means we can find the preorder traversal of the left and right subtree is based off ‘idx’ value.

This means we know the size of the left and right subtree, we can also find the preorder traversal of the left and subtree as well (I will explain why this is correct below). Pre-order traversal covers the tree in “Node-Left-Right” order, so everything from indexes 1…idx has to include everything that is left of the root node because everything after — from idx+1…n-1 — must be right of the node (right subtree). These are isolated as the preorder traversals of the left and right subtree.

Now we have preorder and inorder traversals of each left and right subtrees of the root node, and we recursively call the function with these smaller inputs. Both of these subtrees have preorder and inorder traversals that are less than n, which means that by our inductive hypothesis, these recursive calls must return the correct answers, as both preorder and inorder don’t include the root node (thus giving their size an upper bound of n-1).

Now that we have the correct left and right subtree, merging our solution is easy: all we have to do is assign the left and right subtree accordingly (line 6,7). This merged solution is ready to be returned (line 8).

Inductively, we have proven that for any tree of size n, if we are given it’s preorder and inorder traversal arrays, we can reconstruct the tree. A Python version of the code will be included below:

Actual Code

Runtime Analysis

Runtime: Intuitively, our runtime of our algorithm is O(nlogn). This is because our algorithm performs an O(n) operation of finding the ‘idx’ variable in the inorder array on each function call, and there are log(n) function calls: this is because we split the array each time (approximately in half), which leads to at most log_2(n) calls.