ptcr 0.1.6

Constructs and simulates PTCR models.

Exploring Alternative Cost Mechanisms for Probabilistic Planning

Author: T-Lind

Overview

"An important class of applications entails a robot monitoring, scrutinizing, or recording the evolution of an uncertain time-extended process. This sort of situation leads to an interesting family of planning problems in which the robot is limited in what it sees and must, thus, choose what to pay attention to. The distinguishing characteristic of this setting is that the robot has influence over what it captures via its sensors, but exercises no causal authority over the evolving process. As such, the robot’s objective is to observe the underlying process and to produce a ‘chronicle’ of occurrent events, subject to a goal specification of the sorts of event sequences that may be of interest. This paper examines variants of such problems when the robot aims to collect sets of observations to meet a rich specification of their sequential structure. We study this class of problems by modeling a stochastic process via a variant of a hidden Markov model, and specify the event sequences of interest as a regular language, developing a vocabulary of ‘mutators’ that enable sophisticated requirements to be expressed. Under different suppositions about the information gleaned about the event model, we formulate and solve different planning problems. The core underlying idea is the construction of a product between the event model and a specification automaton.

"A concrete motivation for this sort of setting, consider the proliferation of home videos. These videos are, with remarkably few exceptions, crummy specimens of the cinematic arts. They fail, generally, to establish and then bracket a scene; they often founder in emphasizing the importance of key subjects within the developing action, and are usually unsuccessful in attempts to trace an evolving narrative arc. And the current generation of autonomous personal robots and video drones, in their roles as costly and glorified ‘selfie sticks,’ are set to follow suit. The trouble is that capturing footage to tell a story is challenging. A camera can only record what you point it toward, so part of the difficulty stems from the fact that you can’t know exactly how the scene will unfold before it actually does. Moreover, what constitutes structure isn’t easily summed up with a few trite quantities. Another part of the challenge, of course, is that one has only limited time to capture video footage. Setting aside pure vanity as a motivator, many applications can be cast as the problem of producing a finite-length sensor-based recording of the evolution of some process. As the video example emphasizes, one might be interested in recordings that meet rich specifications of the event sequences that are of interest. When the evolution of the event-generating process is uncertain/nondeterministic and sensing is local (necessitating its active direction), then one encounters an instance from this class of problem. The broad class encompasses many monitoring and surveillance scenarios. An important characteristic of such settings is that the robot has influence over what it captures via its sensors, but cannot control the process of interest. Our incursion into this class of problem involves two lines of attack. The first is a wide-embracing formulation in which we pose a general stochastic model, including aspects of hidden/latent state, simultaneity of event occurrence, and various assumptions on the form of observability. Secondly, we specify the sequences of interest via a deterministic finite automaton (DFA), and we define several language mutators, which permit composition and refinement of specification DFAs, allowing for rich descriptions of desirable event sequences. The two parts are brought together via our approach to planning: we show how to compute an optimal policy (to satisfy the specifications as quickly as possible) via a form of product automaton. Empirical evidence from simulation experiments attests to the feasibility of this approach. Beyond the pragmatics of planning, a theoretical contribution of the paper is to prove a result on representation independence of the specifications. That is, though multiple distinct DFAs may express the same regular language and despite the DFA being involved directly in constructing the product automaton used to solve the planning problem, we show that it is merely the language expressed that affects the resulting optimal solution. Returning to mutators that transform DFAs, enabling easy expression of sophisticated requirements, we distinguish when mutators preserve representational independence too."

Additionally, a cost-based optimization approach has been implemented, such that the optimal policy becomes the one that reduces the most amount of cost, while still satisfying the constraints of the problem. This could mean minimizing the distance a robot travels, reducing its wear and improving its efficiency, minimizing the amount of time it takes to complete a certain task.

Example Usage

{
  "state_names": ["I", "E", "B", "C", "D", "S"],
  "transition_matrix": [
    [0.0, 0.1, 0.3, 0.1, 0.2, 0.3],
    [0.0, 0.1, 0.2, 0.1, 0.3, 0.3],
    [0.0, 0.2, 0.1, 0.1, 0.3, 0.3],
    [0.0, 0.1, 0.2, 0.2, 0.3, 0.2],
    [0.0, 0.2, 0.3, 0.1, 0.1, 0.3],
    [0.0, 0.4, 0.2, 0.2, 0.2, 0.0]
  ],
  "cost_matrix": [
    [1, 5, 2, 3, 2, 1],
    [1, 1, 5, 2, 3, 4],
    [2, 1, 1, 1, 2, 3],
    [3, 2, 5, 1, 1, 4],
    [2, 5, 2, 5, 1, 4],
    [5, 2, 3, 2, 4, 1]
  ],

  "initial_distribution": [0.0, 0.1, 0.3, 0.2, 0.2, 0.2],
  "state_events": [
      [[], ["e1"], ["b1"], ["c1"], ["d1"], ["s1"]],
      [[], ["e2"], ["b2"], ["c2"], ["d2"], ["s2"]],
      [[], ["e3"], ["b3"], ["c3"], ["d3"], ["s3"]]
    ],
  "single_initial_states": [
    [[["d1", "d2"], "d12"]],
    [[["d2", "d3"], "d23"]]
  ],

  "alphabet": ["e1", "b1", "c1", "d1", "s1", "e2", "b2", "c2", "d2", "s2", "d12", "e3", "b3", "c3", "d3", "s3", "d23"],

  "plot": true,
  "log": true
}

Demonstrate capabilities:

import json
from timeit import default_timer as timer

import numpy as np
from scipy.stats import ttest_ind
from tqdm import tqdm

from ptcr2.fom import FOM

config_file = 'samples/wedding_fom.json'

with open(config_file) as f:
    spec = json.loads(f.read())

wedding_fom_cost = FOM()
start = timer()
wedding_fom_cost.compute_optimal_policy(spec, cost_based=True)
end = timer()

print('Time elapsed to compute cost-based optimal policy: ', end - start)

wedding_fom_no_cost = FOM()
start = timer()
wedding_fom_no_cost.compute_optimal_policy(spec)
end = timer()

print('Time elapsed to compute no-cost optimal policy: ', end - start)

# Load the two models
wedding_fom_cost = FOM.load('saves/wedding_fom_cost.pkl')
wedding_fom_no_cost = FOM.load('saves/wedding_fom_no_cost.pkl')

# Example run
result_no_cost = wedding_fom_no_cost.simulate_general_and_greedy_algorithms()
print(result_no_cost)
result_cost = wedding_fom_cost.simulate_general_and_greedy_algorithms()
print(result_cost)

# Now, simulate the algorithms across 1000 runs
n_runs = 1_000

no_cost_steps = []
no_cost_costs = []

cost_steps = []
cost_costs = []

for _ in tqdm(range(n_runs)):
    result_no_cost = wedding_fom_no_cost.simulate()
    no_cost_steps.append(result_no_cost['steps'])
    no_cost_costs.append(result_no_cost['total_cost'])

    result_cost = wedding_fom_cost.simulate()
    cost_steps.append(result_cost['steps'])
    cost_costs.append(result_cost['total_cost'])

# Print 5-number summary + mean for general and greedy steps taken
print('Costless Algorithm Steps Summary:')
print('Min:', np.min(no_cost_steps))
print('Q1:', np.percentile(no_cost_steps, 25))
print('Median:', np.median(no_cost_steps))
print('Mean:', np.mean(no_cost_steps))
print('Q3:', np.percentile(no_cost_steps, 75))
print('Max:', np.max(no_cost_steps))

print('\nCost-Optimized Algorithm Steps Summary:')
print('Min:', np.min(cost_steps))
print('Q1:', np.percentile(cost_steps, 25))
print('Median:', np.median(cost_steps))
print('Mean:', np.mean(cost_steps))
print('Q3:', np.percentile(cost_steps, 75))
print('Max:', np.max(cost_steps))

# Print 5-number summary + mean for general and greedy costs incurred
print('\nCostless Algorithm Costs Summary:')
print('Min:', np.min(no_cost_costs))
print('Q1:', np.percentile(no_cost_costs, 25))
print('Median:', np.median(no_cost_costs))
print('Mean:', np.mean(no_cost_costs))
print('Q3:', np.percentile(no_cost_costs, 75))
print('Max:', np.max(no_cost_costs))

print('\nCost-Optimized Algorithm Costs Summary:')
print('Min:', np.min(cost_costs))
print('Q1:', np.percentile(cost_costs, 25))
print('Median:', np.median(cost_costs))
print('Mean:', np.mean(cost_costs))
print('Q3:', np.percentile(cost_costs, 75))
print('Max:', np.max(cost_costs))

alpha = 0.05

# We want to check if both the number of steps and cost is lower for the cost-optimized algorithm than the costless algorithm
t_stat, p_val = ttest_ind(cost_steps, no_cost_steps, equal_var=False, alternative='less')
print("Performing 2-sample t-test to compare costless and cost-optimized algorithms:")
print('T-Statistic:', t_stat)
print('P-Value:', p_val)

if p_val < alpha:
    print(
        'Reject the null hypothesis: The cost-optimized algorithm is significantly lower in steps than the costless algorithm.')
else:
    print(
        'Fail to reject the null hypothesis: The cost-optimized algorithm is not significantly lower in steps than the costless algorithm.')

# Perform an independent 2-sample t-test to determine if the cost-optimized algorithm is significantly lower in cost than the costless algorithm
t_stat, p_val = ttest_ind(cost_costs, no_cost_costs, equal_var=False, alternative='less')
print("\nPerforming 2-sample t-test to compare costless and cost-optimized algorithms:")
print('T-Statistic:', t_stat)
print('P-Value:', p_val)

if p_val < alpha:
    print(
        'Reject the null hypothesis: The cost-optimized algorithm is significantly lower in cost than the costless algorithm.')
else:
    print(
        'Fail to reject the null hypothesis: The cost-optimized algorithm is not significantly lower in cost than the costless algorithm.')

Questions?

If you have any questions, feel free to reach out to me at [e-mail].

Acknowledgements

Dylan A. Shell

Hazhar Rahmani