\section{Introduction}
\input{sections/01_introduction}

\section{Related Works}
\input{sections/02_relatedwork}

\section{Formative Study}
\input{sections/03_formativestudy}

\section{Scrapbook{}: Design and Implementation}
\input{sections/04_prototype}

\section{Evaluation: A Week-Long Usability Study}
\input{sections/05_method}

\section{Results}
\input{sections/06_result}

\section{Discussion and Future Work}
\input{sections/07_discussion}

\section{Conclusions}
\input{sections/08_conclusion}

\begin{acks}
We thank all the reviewers for their thorough feedback. We are also grateful to all user study participants for their participation and sharing their screenshot data.
\end{acks}

\bibliographystyle{ACM-Reference-Format}

\subsection{Users' Challenges in Resource Management}
Modern knowledge workers multitask routinely, with many applications, files, and web pages open at once.
Gonzalez and Mark found that while modern knowledge workers deal with more than 10 distinct tasks per day, they spend an average of just 12 minutes on a particular activity before being interrupted~\cite{gonzalez2004constant}.
A similar study stated that information workers usually spend less than one hour on a project before switching to another task~\cite{czerwinski2004diary}.
Given the inevitability of interruptions and frequent changes in working contexts, workers may encounter many resources of various types that they wish to curate, but curation activities---storing files, bookmarking web pages, opening files, and locating a web page---can degrade their working productivity.
For example, one study found that programmers usually spend more than one hour every day managing their working resources and projects to reduce time spent on recalling and retrieving them later~\cite{van1998interrupts}.
Furthermore, spending time retrieving a past working context to restart an unfinished task can contribute to stress and negative emotions~\cite{czerwinski2004diary, mark2015focused}.
Therefore, reducing the time spent curating resources would enhance computer users’ productivity.

\subsection{Tools for Organizing Digital Resources}
Curating digital resources on a computer involves various activities associated with organizing information and software, including seeking, discovering, organizing, using, and sharing.
\ADD{Researchers found that information scraps in personal information management systems should be easy to capture and discover~\cite{bernstein2008information}.}
Digital curation activities can range from basic, low-level tasks like saving a file to complex, high-level tasks like creating and maintaining an organized hierarchy of nested folders.
Early HCI researchers focused on organizing multiple active windows based on tasks.
For example, GroupBar allows users to manage windows in a batch grouped by task and expand and minimize batches of documents, which can be helpful for switching between tasks~\cite{smith2003groupbar}.
Scalable Fabric organizes thumbnail-like windows into groups near the edges of a computer's screen for workers to quickly switch between windows by clicking a thumbnail of the window~\cite{voida2008re}.
\ADD{Giornata similarly allows users to have a virtual desktop per activity~\cite{swearngin2021scraps}.}
TaskTracer applies machine learning algorithms to bundle various resources into a task~\cite{Dragunov:2005:TDE:1040830.1040855_tasktracer}.
\ADD{Some researchers distributed the effort needed to curate resources by inserting microtasks when users are interrupted~\cite{teevan2014selfsourcing}.
Inserting such microtasks was helpful for task resumption as well~\cite{williams2019mercury}.
Capturing context and transferring resources across devices can be challenging, as workers may use a variety of devices for a task~\cite{swearngin2021scraps}. }\marking{1}
\ADD{Furthermore, to manage and handle scattered digital information, researchers have proposed various technical methods to facilitate task-based computing activities and improve the efficiency of microproductivity~\cite{ bernstein2007management, shen2008automatically, oleksik2009lightweight}.}\marking{1}
\ADD{These approaches provide effective means of bundling or curating task resources in the context of window management for multitasking and cross-device work support, assisting users in quickly switching between tasks and curating resources on the go.}

In contrast, Scrapbook{} provides tools for knowledge workers to curate digital resources for various purposes in a longer term with visual cues: bookmarking an article, initializing a computing environment for task resumption, saving multiple resources related to a given resource, or keeping track of unfinished tasks for mental reconstruction.

With the proliferation of web-based resources and applications, researchers have developed many tools for managing web resources.
One native, widely used tool in modern web browsers is the bookmark function.
However, researchers have found that as a user's number of bookmarks increases, browsing, locating, and retrieving web pages becomes more challenging, ultimately requiring organizational efforts comparable to those applied to file systems: users must establish a hierarchical structure of bookmark folders, name bookmarks carefully, and categorize them immediately upon creation~\cite{10.1145/274644.274651}.
\ADD{Cockburn et al. found that web users maintain large collections of bookmarks, nearly 200 on average, thereby yielding a lengthy list of bookmarks with folders~\cite{cockburn2001web}.
The authors found empirical evidence demonstrating that users do not carefully curate bookmarks: imbalances between deletion and addition lead to the appearance of duplicate and invalid bookmarks.}
The limitations of native implementations of bookmarking may account for the popularity of commercial apps like Pocket~\footnote{\url{https://getpocket.com/}} and Pinterest~\footnote{\url{https://www.pinterest.com}}, which enable social bookmarking and provide multimodal cues (images and text) to facilitate web content curation.
Similarly, collaborative web browsing and bookmarking was shown to be an effective curation method for a specific task~\cite{10.1145/1294211.1294215}.
Recently, researchers have developed ways to organize multiple tabs based on search keywords~\cite{10.1145/1357054.1357242}, themes~\cite{10.1145/3173574.3173825}, or tasks~\cite{10.1145/3472749.3474777}.
While these tools facilitate effective resource curation, they do not allow workers to curate resources across applications.

\subsection{Using Visual Cues and Screenshots to Reconstruct a Working Context}
\label{sec:visual}
Researchers have found that human beings can remember visual information at scale~\cite{brady2008visual}.
Standing et al. found that humans were able to determine whether they had seen an image two days ago with 90\% accuracy among a collection of 2560 pictures~\cite{standing1970perception}.
Sellen et al. ran a case study and found that humans could correctly identify images of their own among those of others with over 80\% accuracy in life-logging context~\cite{sellen2007life}.
In addition, visual information can be processed in parallel, meaning that a human can recognize an image at a glance; conversely, humans cannot recognize a block of text visually and must parse it for meaning~\cite{WARE20211}.
These results indicate that humans are able to discriminate between similar images, recall detailed contexts, and remember related past activities from images.

The human ability to recall details from visuals has often been used in the context of computing as well.
In one study, Czerwinski and Horvitz stated that video footages of a worker using a computer serve as effective cues for people to recall past events even after one month~\cite{czerwinski2002investigation}.
The recall capability by seeing computer recording was developed into a research method---usability testing with retrospective recall as an alternative to the think-aloud technique~\cite{russell2009retrospective, russell2014looking}.
Application windows serve as visual cues for knowledge workers to understand which (sub)tasks need to be finished when workers resume a task~\cite{iqbal2007disruption, ko2005eliciting}.
In programming environments, researchers implemented methods to display snippets of edited code blocks to help programmers resume past coding and debugging tasks~\cite{safer2007comparing, parnin2010evaluating}.
Modern smartphone users take advantage of the ubiquity of smartphone cameras with the practice of taking photos to serve as external memory devices; for instance, a user might take a photo of a pillar to recall their car's location in an airport parking lot or take a screenshot of mobile phone to save a QR code of a flight ticket~\cite{Finley2018}.
In this work, the metaphor of photo album was used for the Collective View in Scrapbook{} design.

Many HCI researchers have leveraged the human ability to comprehend visual information in creating productivity tools for mental reconstruction and task resumption.
For example, \revise{Taskpos{\'e} arranges thumbnails of windows based on their relevance to an ongoing task, helping users to manage multiple windows based on usage patterns and transitions between them~\cite{Bernstein:2008:TEF:1449715.1449753}.}
A precursor to this work is WindowScape, which allows users to capture a group of windows on a screenshot to switch between digital work spaces~\cite{10.1145/2147783.2147791}.
However, these systems only allow transitions between already open windows; consequently, they do not address the challenge of long-term resource curation and retrieval that workers face.
Another application of screenshots explored in numerous studies lies in creating a visual history to help users recall the mental context of their computing activities in the past.
Rule et al. investigated the benefits of using a visual history for mental reconstruction and arrived at design implications by exploring various design options (animation vs. still image, thumbnail size) and their effects~\cite{rule2015restoring, rule2017using}.
ScreenTrack generates a time-lapse video by capturing screenshots periodically; workers can reopen the frontmost application from any frame of the video and use the video to reconstruct their mental context~\cite{hu2020screentrack}.
While these systems and the present work share the goal of facilitating mental reconstruction, they differ from Scrapbook{} in as much as they visualize screenshots in the temporal dimension rather than using them for explicit curatio
\iffalse
Scrapbook{} draws ideas from these works and allows users to maintain a collection of screenshots for various purposes.
In addition, Scrapbook{} pairs visual cues with symbolic information (viz., text) to make curation multimodal
Christel et al. stated that the combination of textual and visual methods can significantly improve both recall and comprehension compared to either text or images alone~\cite{christel2002collages}.
Using multimodal information has been found to be effective in helping users recall past events and retrieve information~\cite{fouse2011chronoviz, grossman2010chronicle, bernstein2008taskpose, russell2009retrospective, yoon2013visualization}.
Combining symbolic information with screenshots makes the approach of Scrapbook{} scalable by allowing users to search with keywords or filter screenshots by time range.
\fi

\subsection{Participants and Survey}
We designed an online questionnaire to investigate what computer users think of current curation methods and personal task resumption methods.
We created an online survey with questions in the following categories: (1) features that users use for web pages and file curation, (2) challenges for task resumption, and (3) demographic questions.
The survey included five-point scale items prompting users to report their feature usage frequency, as well as open-ended questions.
Respondents were recruited through a variety of channels: the author's social media accounts, Amazon Mechanical Turk, and campus mailing lists.
In each case, eligibility criteria posted with the survey indicated that respondents should be modern computer users who use computers in their work.
In total, we received 125 responses from these platforms after excluding those responses that did not pass attention check questions.
Each participant received a \$5 e-gift card for their participation.
Respondents had an average age of 32.6 years; 63 were male, 60 were female, and 2 chose not to provide their gender.
Out of the 125 respondents, 115 had at least some form of college degree, and 118 rated their digital literacy as average or above.
Participants reported spending an average of 8.6 hours per day using computers for daily tasks.

\begin{figure}[t]
\centering
  \includegraphics[width=\columnwidth]{sections/Images/bookmarkv.png}
  \caption{Participants' ratings of how frequently they use different methods to revisit a website. The upper bar graph illustrates the proportion of reported usage frequencies for the listed methods of opening regularly visited websites. The lower graph illustrates the proportion of reported usage frequencies for the listed methods of reopening needed websites that respondents did not visit regularly.}
  ~\label{fig:bookmarks}
\end{figure}
\subsection{Results}
\subsubsection{Bookmarks are infrequently utilized.}

We calculated descriptive statistics for the five-point scale items, and the first author conducted a thematic analysis of the open-ended responses to generate codes. The codes and themes were reviewed by both authors and iteratively coded the responses until common themes emerged from the data.

We asked participants how often (``never,'' ``rarely,'' ``sometimes,'' ``often,'' or ``always'') they used built-in web browser functionality to visit websites in two categories: regularly visited sites (such as YouTube or Amazon) and sites they do not visit regularly but wish to revisit.
The results indicate that the resource management features web browsers provide---namely, bookmarks and a browsing history---are not the most frequently used methods for revisiting websites.
For regularly visited websites, users tend to simply type their URLs in the address bar; for irregularly visited sites, users repeat keyword searches to find the sites again (see Figure~\ref{fig:bookmarks}.).
Bookmarks are the second most used function in both cases.
While Bookmarking would be the function dedicated to resource curation, it is not the most frequently used method of revisiting websites, being the less-used method than relying on their memory (URLs, keywords) or searching it from scratch (search engine).
This result is consistent with a previous work which found that history and bookmarking mechanisms provided by browsers can be ineffective~\cite{10.1145/274644.274651, weinreich2006off}.

We further asked about the inconvenience of using bookmarks in web browsers in an open-ended question.
The most common answers (38/125) mentioned that curating bookmarks is time-consuming and bookmarks are ``cumbersome to keep organized (P52).''
Participants complained about having to give bookmarks recognizable names and place them in the right folders.
Similarly, some participants (21/125) complained about the difficulty of finding a desired bookmark, especially when bookmarks lack descriptive labels.
Other responses were associated with the scale of bookmark collections, pointing out the challenge of locating a desired bookmark within a large field of irrelevant ones.
They pointed out that they simply had too many bookmarks (20/125), and sometimes, they even forgot about what pages they had bookmarked (18/125).
These responses clearly show that bookmarks are not scalable from a certain point.
Evidently, having to organize bookmarks to later recognize them easily is the biggest challenge in using bookmarks.

\subsubsection{Users get lost in folder hierarchies.}

Survey respondents most commonly use their operating system's native file manager (e.g., Finder, Windows Explorer) to curate files; 70 out of 125 chose Often or Always.
Arranging files on the desktop was also identified as a common approach (Often/Always: 58 out of 125) to saving frequently accessed documents and files.
Other less commonly used features were recent documents and search features (e.g., Spotlight, Everything).
Search features were used especially when users could not locate files by other means.

Mirroring the situation with bookmarks, the biggest concern respondents had regarding retrieving files was not being able to locate files or paths to files (48/125).
P16's response exemplifies the challenges of remembering file locations:
\begin{quote}[P16]
"When I'm trying to find a file and don't remember where I saved it, I'll type in what the title is and sometimes I can't remember what the document is titled."
\end{quote}
\noindent In addition, recognizing poorly named files (19/125) and navigating a folder hierarchy (18/125) were named as challenges.
P20's response demonstrates the cost of organizing files immediately upon saving them, which can impact a later retrieval task:
\begin{quote}[P20]
"I name files something that makes sense at the time while I'm in a rush, but then have trouble recalling where I put it or what that name means."
\end{quote}
\noindent Lastly, while we did not specifically check the portion of users using tools other than file systems, we realize that users have a variety of choices, which increases the number of platforms involved in curation: folder hierarchies, desktops, cloud file systems (e.g., Google Drive and Dropbox), bibliography software, browser bookmarks, and code repositories, to name a few.

\subsubsection{Multiple Challenges: Recall, Locating, and Retrieval}
\label{sec:multiple:challenges}
We asked the participants about the kinds of challenges they face in restoring working contexts in an open-ended question.
Many participants (58/125) reported that the need to track where they left off when they resume a task is their biggest concern---to reconstruct their mental context.
Thus, knowing the context of what needs to be retrieved is the biggest challenge.
The second most common theme (38/125) was retrieving resources as a challenge in resuming a task.
In addition to these challenges, many participants pointed out the relationship between resource retrieval and the burden of organizing resources: resources collected haphazardly are challenging to locate later.
\begin{quote}[P70]
"The biggest challenge is finding it again. Having things organized takes forethought and time."
\end{quote}
 \begin{quote}[P32]
"Having multiple versions of a file saved and remembering which one I was working on because I named them inefficiently."
\end{quote}
\noindent To address these challenges, many participants (56/125) responded that they often leave windows open.
In general, leaving too many applications open can impact a computer's performance and create visual clutter, ultimately making it more challenging for users to locate desired resources.

\subsection{Screenshot-Based Bookmarking for Cross-Application Resources}
In Scrapbook{}, we use a screenshot as a handle to store digital resources in a bundle.
The items visible on a computer screen have already been used as a visual cue to help workers reconstruct their mental context~\cite{iqbal2007disruption, ko2005eliciting, safer2007comparing, parnin2010evaluating}.
One benefit of using images of a computer screen is that all software with a graphical user interface (GUI) inherently affects what is shown on the screen, enabling a curation method for cross-application resources.
While existing works often capture an active window on a screenshot~\cite{bernstein2008taskpose, hu2020screentrack, ScalableFabric}, this approach is limited to one window or the frontmost application, thereby excluding resources underneath the frontmost window that may be relevant to the task.
In practice, even when one is under the other in terms of its order, two windows can be laid out side by side so that both windows are fully visible.
In Scrapbook{}, a user can bundle multiple resources that are commonly used together.
Lastly, we anticipate that users will quickly recognize the contents of a screenshot at a glance and recall the context in which they took a screenshot based on the human capability to process visual information introduced in~\ref{sec:visual}.
\ADD{The benefit of visual cues will alleviate the challenge users face in reconstructing their mental context identified in the formative study, and the simple interaction of capturing a screenshot will reduce the burden of curating resources.}\marking{2}

Scrapbook{} provides two screenshot capture options: capturing a screenshot by selecting an area (the first button in Figure~\ref{fig:MenuBar}) and taking a full-screen screenshot (the second button in Figure~\ref{fig:MenuBar}).
The former is intended for use in targeting a specific application or a specific region of a screen (e.g., a figure in an academic paper).
These options resemble the capture options available in an operating system's native screenshot functionality.
\ADD{We anticipate that the simplicity and universality of curating any visible resource with a single click will help to reduce knowledge workers' burden of expressly choosing a curation method per resource type.}\marking{3}

\begin{figure}[t]
  \centering
  \includegraphics[width=0.80\columnwidth]{sections/Images/MenuBar.png}
  \caption{The Scrapbook popup menu. This menu pops up when users click the "S" icon in the menu bar. Users can take screenshots with the first two buttons to capture their current computer activities. Clicking the Collection View opens the UI shown in Figure~\ref{fig:collectionView}.}
  \label{fig:MenuBar}
  \Description{}

\end{figure}

\subsection{Extracting Metadata per Resource}

Scrapbook{} extracts all available metadata from each window visible in a screenshot.
While a screenshot may help a user reconstruct their mental context, a screenshot alone cannot open a file, an application, or a web page depicted therein.
Therefore, metadata, such as file names, URLs, file paths, and application paths, is essential in reopening applications.
We use an operating-system-level accessibility API to extract metadata.
\ADD{Combined with a screenshot, this metadata practically eliminates the challenge of locating resources immediately after recalling them from an image, which was one of three challenges we found in the formative study. }

In addition to the metadata mentioned above, Scrapbook{} collects other information that may assist users when using the search feature, such as application names, web page titles, window titles (which may not simply be the names of open files), or any user-provided data they may choose to add.
For instance, a user may be able to resume reading a paper by searching for its title and finding a PDF viewer window whose title contains the paper's title.
Therefore, Scrapbook{} will provide \textit{multimodal}---visual, temporal, and textual---cues that users can rely on to locate a screenshot, which will be discussed in ~\ref{fig:collectionview}.

\subsection{Identification of Visible Captured Applications}

Scrapbook{} identifies visible windows from a screenshot using a bit-masking algorithm.
The appearance of a screenshot depends in part on how a user arranges their windows.
For example, in a simple case, a user may use only one window at a time in full-screen mode.
Conversely, some users may use ultra-wide monitors or arrays of several monitors to view multiple large windows at once.
In a more complicated case, a user may want to include a partially visible window in a screenshot, such a window header of a relevant resource that is partially visible behind the main resource window.
A complex example is shown in Figure~\ref{fig:algorithm}-a; note that all four windows in the example are, at least partially, visible.
While Scrapbook{} can extract metadata regarding every window's location --- its width, height, the coordinates of its upper-left corner, and its ``depth'' among other windows, it does not explicitly determine what portion of any window is visible.
The visible region of Window 3 in Figure~\ref{fig:algorithm}-a, for example, is an irregular, concave octagon, which makes it difficult to evaluate whether the window is visible or not by simply knowing its size and location; it depends on where the windows above it (1 and 2, in this case) are located.
The simplest possible solution is to capture only the frontmost application, but this would prevent our tool from capturing multiple resources.
Capturing all open applications is another option, but this may force a user to remove/deselect irrelevant windows when users retrieve resources from a screenshot.
Therefore, we identify the visibility of each window by running a bit-masking algorithm (see Figure~\ref{fig:algorithm} and Algorithm~\ref{Algorithmpseudocode}).

\begin{figure}[t]
  \centering
  \includegraphics[width=\columnwidth]{sections/Images/AlgorithmFig1.png}
  \caption{Step-by-step illustration of the bit-masking algorithm. (a) Suppose there are four windows 1--4 in that order (left) and a user takes a selected area screenshot (right; selected area of interest highlighted in red). (b) The algorithm sees the intersection between Window 1 and the selection to determine the visibility of the window within the screenshot (left). If visible, it updates the area of interest by excluding the intersection, as any following windows in the area will be occluded by Window 1. (c) Given the updated area of interest, examine the next window available until there is no window to examine or the area of interest is too small.}
  \label{fig:algorithm}
  \Description{Algorithm Demonstration}

\end{figure}

\begin{algorithm}[t]
\caption{\textcolor{black}{Identifying visible windows on a screenshot.} Matrices are denoted by italicized capital letters. Non-italicized capital letters use set notation. The dimensions of all matrices are the dimensions of the computer screen after downsampling.}
	\label{Algorithmpseudocode}
 	\begin{algorithmic}[1]
	    \STATE let {$A$} = [$a_{(i,j)}$], where \COMMENT{\textcolor{purple}{$A$: Area of Interest Matrix}}
	    \[a_{(i,j)}=\left\{\begin{array}{cl}
1,& \mbox{if (i,j) in screenshot area}\\
0,& \mbox{elsewhere}\end{array}\right.\]
        \STATE let V = \{ \}  \COMMENT{\textcolor{purple}{set of visible window index, empty set initially}}
		\FORALL{Window$_k$=1,2, $\ldots$, n  \COMMENT{\textcolor{purple}{n: the \# of windows on screen}}}

        \STATE let {$W_k$} = [$w_{k,(i,j)}$], where \COMMENT{\textcolor{purple}{$W_k$: the \textit{k}th Window Matrix}}
 	    \[w_{k,(i,j)}=\left\{\begin{array}{cl}
 1,& \mbox{if (i,j) in the $k$th Window area}\\
 0,& \mbox{elsewhere}\end{array}\right.\]
            \STATE let {$O_k$} = [$o_{k,(i,j)}$], where \COMMENT{\textcolor{purple}{(O$_k$ = W$_k$ $\cap$ A)}}
            	    \[o_{k,(i,j)}=w_{k,(i,j)} \&  a_{(i,j)}\]
    	    \IF{$elementSum(O_k) > threshold$}
    	        \STATE V.add(k) \COMMENT{\textcolor{purple}{the $k$th Window is visible.}}
	        \ENDIF
	        \STATE update {$A$} = [$a_{(i,j)}$], where \COMMENT{\textcolor{purple}{(A = A - W$_k$)}}
            	    \[a_{(i,j)} \gets a_{(i,j)} \&  \neg w_{(i,j)}\]
    	    \IF{$elementSum(A) \leq threshold$}
                \STATE break; \COMMENT{\textcolor{purple}{Area of interest smaller than threshold}}

	        \ENDIF

		\ENDFOR\\
		\RETURN V \COMMENT{\textcolor{purple}{Return the set of visible window index}}
 	\end{algorithmic}
\end{algorithm}

The core idea of the bit-masking algorithm is to dynamically maintain a matrix, denoted by A in Algorithm~\ref{Algorithmpseudocode}, that represents an area of interest considering the occlusion between windows.
For example, initially, each element $a_{(i,j)}$ of matrix A is 1 if the element is within the screenshot area (Figure~\ref{fig:algorithm}-a-Right; line 1 in Algorithm~\ref{Algorithmpseudocode})---if a user takes a full-screen screenshot, A will be a matrix of ones.
Then, the algorithm iterates over each open window from the frontmost to rearmost to see if there is any intersection between the area of interest and a window area (lines 4 and 5).
If there is an intersection and the intersection is greater than a threshold value (line 6), the target window is determined to be (sufficiently) visible in the screenshot (Figure~\ref{fig:algorithm}-b-Left, line 7).
Next, the area of interest is updated before moving on to the next window to exclude the region of the most recent visible window; whatever is underneath the window will be invisible. (Figure~\ref{fig:algorithm}-b-Right, line 9)
The algorithm repeats the intersection check (Figure~\ref{fig:algorithm}-b, c, d, Left) and updates the area of interest (Figure~\ref{fig:algorithm}-b, c, d, Right) until there is no window left on the screen or the area of interest is smaller than a threshold value (Figure~\ref{fig:algorithm}-d-Right, line 10-12).
We reduced the computational load of the algorithm by downsampling the screen and all window sizes/locations. Also, by setting the threshold value, we can filter out small windows that are unlikely to contain meaningful information.
If the downsampling ratio is 10 pixels in length and the threshold is 5, the algorithm will ignore any window whose visible area is less than 500 (e.g., a 50~×~10 area).
In the example of Figure~\ref{fig:algorithm}, the algorithm might have ended after Window 2 if the area of interest (e.g., Figure~\ref{fig:algorithm}-c-Right) were smaller than the threshold.
We used 0 for the threshold value for the sake of simplicity; users would be able to understand that Scrapbook{} will capture any resource that is visible on a screen, no matter how small the visible part is.
The visibility identified per window will be used to recommend which application to open, discussed in~\ref{sec:detailedView}.
\begin{figure}

    \begin{subfigure}[b]{\linewidth}
        \centering
              \vspace{-10px}

        \includegraphics[width=\linewidth]{sections/Images/capturedViewImage.pdf}
        \caption{Captured View
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{\linewidth}
        \centering
        \includegraphics[width=\linewidth]{sections/Images/detailedViewImage.pdf}
        \caption{Detailed View

    \end{subfigure}
\caption{(a) The Captured View appears after a user takes a screenshot to curate their resources; in this case, a PDF of an academic paper and an Overleaf project. (b) In Detailed View, users can view more details about a task. The example shows the task of planning a trip across multiple applications.}\label{fig:detailedView}
\label{fig:twoViews}
\end{figure}

\subsection{Browsing a Screenshot Collection}
\label{fig:collectionview}
The design used to present curated screenshots may influence the effectiveness of Scrapbook{}.
For example, there is a trade-off between the screenshot size and the number of images that can be displayed within a full-screen window simultaneously.
Conversely, larger thumbnails can promote more accurate mental context recall~\cite{rule2017using}.
We chose to provide two different views: the Collection View, which shows a collection of screenshots; and the Detail View, which shows a single screenshot.
\ADD{The Detail View assists users in the challenge of recognizing content from its bookmark handle with rich, visual cues available in a screenshot; conversely, the Collection View reduces the cost to users of having to organize bookmarks by linearly presenting them like a photo album.}\marking{2}
We will share the Collection View design in this section and Detail View in the following section.

Users can access their curated screenshots in the Collection View window~\ref{fig:collectionView}.
The Collection View is the core component that helps users glance at their collections and locate screenshots.
Whenever a user wants to reopen an application from a screenshot or immediately after a user saves a screenshot, the user is routed to the Collection View, providing an opportunity to glance at the collection and reminding them of recently curated screenshots.
The Collection View offers three ways to search for screenshots, in addition to screenshots' visual cues.
The most basic method is skimming screenshots in the temporal dimension by scrolling the screenshot feed.
The Collection View uses a ``Masonry'' layout, patterned on online systems for curation like Pinterest, Google Keep, and photo albums~\cite{Thornburg01}.
Overall, the screenshots are presented in reverse chronological order, with the most recent one in the upper-left corner.
Users can understand the ordering of screenshots through timestamps presented as the time distance between the capture time and the current time (e.g., 3 days ago).
The second way is to search by keywords.
A search bar is located at the top of the interface; users can search for screenshots whose metadata matches their input in any of the following fields: filename, application name, date, URL, window title, and user-supplied data (such as a description or title).
Searching by keyword is helpful in drastically reduce the number of screenshots users must skim, if not to locate the target screenshot immediately.
Lastly, users can like---by pressing heart button---frequently used screenshots to make them appear before others.
This feature is similar to marking important emails with a star, flag, or pin in an email client~\cite{10.1145/2556288.2557013}.
If a user wants to capture the work context of an interrupted task that they want to resume in a short term, starring the screenshot will be useful.

\subsection{Capturing Detail per Screenshot}
\label{sec:detailedView}

Lastly, retrieving resources from a screenshot is a key feature of Scrapbook{}.
Immediately after a user takes a screenshot, the user is given the opportunity to add their own input and select or deselect resources captured from the screenshot in the Capture View (Figure~\ref{fig:detailedView}-(a)).
\ADD{This function helps users contextualize their curation beyond images and captured metadata, similarly to a previous work~\cite{swearngin2021scraps}.
}\marking{2}
Scrapbook{} selects all of the applications initially evaluated as visible by the bit-masking algorithm.
Users have an option to deselect visible applications if they are irrelevant to the task.
Similarly, users can also include invisible apps in the screenshot by expanding the invisible apps and choosing an application to add.
This functionality will be useful in situations where a user switches between two full-screen windows, one of which will always be fully occluded by the other, despite using two resources simultaneously (e.g., Google Scholar and Microsoft Word).
In addition, including invisible resources can facilitate mental reconstruction.
For example, a user may wish to curate an article they encountered (\textit{a curated resource}) while writing a paper about social media (\textit{context}), which might have been invisible on a screenshot.
By including this information, users can understand the context in which they decided to curate a given resource.
Lastly, a user can optionally supply their own information in the Title and Description fields, which may be useful for later searches. The title defaults to the time when the screenshot was taken.
Generally, clicking Save Screenshot will be sufficient if a user simply wants to save the resources visible in the screenshot.
Once saved, Scrapbook{} will display the Collection View to show the most recent screenshot added.

Users can reopen captured resources from the Detailed View (Figure~\ref{fig:detailedView}-(b)) for a screenshot, accessed by clicking any thumbnail in the Collection view.
Scrapbook{} will recommend which applications be opened
Users can choose to open more or less than initially selected by the algorithm, including invisible resources.
In both the Capture View and the Detailed View, images are displayed at maximum size with an option to zoom in to see the original size.
In addition, each resource's metadata (e.g., the application name, window title, and path) will be presented.

\subsection{Implementation}
We designed and implemented Scrapbook{} for Apple's macOS.
The program uses AppleScript to extract metadata from captured applications \ADD{and relaunch applications}.
The process of running AppleScript code and capturing screenshots is accomplished using macOS's native accessibility API.
\ADD{AppleScript supports identifying and opening a specific view in an application with customized per-application scripts, such as a website in browser, a document in Microsoft Word, a project in programming software, or a particular event in a calendar.
For instance, if users capture a screenshot for a document displayed in Microsoft Word, Scrapbook will run predefined AppleScript code based on the captured application and extract metadata, including the file's name and path.
Later, when a user wants to reopen the document, Scrapbook will run additional AppleScript code to launch Microsoft Word and open the target file from the stored local path.}\marking{4}

\ADD{Scrapbook can curate any application and identify corresponding digital resources, provided that the application supports scripting.
In the current design, we mainly consider productivity tools and frequently used applications to cover typical computing tasks, including browsers, the Microsoft Office suite, Apple's iWork suite, programming software, PDF readers, file managers, and text editors.
Furthermore, we designed the software architecture so as to facilitate remotely updating the AppleScript code by maintaining an external CSV file containing customized, application-specific scripts.
}\marking{4}
All metadata and screenshots are stored in a local MongoDB database.
We used Node.js, an open-source, back-end JavaScript runtime environment, to set up a local server for presenting user interfaces, screenshots, and metadata, and to provide a retrieval method in the browser interface.
We developed Scrapbook{} as a window-less application that runs in a menu bar, allowing users to take a screenshot without having to locate the window (Figure~\ref{fig:MenuBar}).

\subsection{Recruitment}

We recruited 13 participants (7 male, 5 female, and 1 non-binary) from the authors' university mailing list and \ADD{the Slack workspace of a research center at the authors' university}.\marking{5}
Participants had an average age of 26.4, ranging from 19 to 37.
The participants were mostly graduate students, as well as two undergraduate students, one software engineer, and one data analyst.
We consider university students to be an eligible target population that shares the challenges that knowledge workers encounter as they use computers as essential devices for research and study; the authors' university requires all university students to have their own personal computing devices when they are admitted.
We limited participants to those who use Apple's macOS operating system for their work or studies on a daily basis.
The average self-assessed daily computer usage time was 9.4 hours ($\sigma$ = 3.4, maximum = 16, minimum = 6).
The results of the pre-study survey indicated that all participants reported their digital literacy~\cite{doi:10.1080/13614533.2015.1137466} as ``above average'' (7/13) or ``excellent'' (6/13) on a five-point scale (``poor,'' ``below average,'' ``average,'' ``above average,'' and ``excellent'').

\subsection{Field Study}
The entire study was done remotely.
Initially, we held a remote meeting in which the first author demonstrated how to use Scrapbook{}; guided participants to install Scrapbook{} and required services (e.g., MongoDB, Node.js) on their computers; explained details and requirements concerning the user study, and asked them to fill out a demographic survey.
After the meeting, we instructed participants to use their computers for their daily computing tasks as usual for a week.
We asked them to use Scrapbook{} during that time to curate digital resources and take a few screenshots each day.
\ADD{Participants were not otherwise instructed to perform specific tasks on their computers.}\marking{5}
After one week of using Scrapbook{}, we conducted a semi-structured interview with participants to ask them questions about their experience of using Scrapbook{}.
Most of the questions concerned how participants used Scrapbook{}, their motivation for taking screenshots, how they liked or disliked the system, and what concerns or suggested improvements they had for the system. For a full list of interview questions, see the appendix.
The initial meeting and exit interview took about 1.5 hours, and participants were compensated with e-gift cards worth \$40.

\subsection{Data Collection and Analysis}

We calculated descriptive statistics on participants' use of Scrapbook{} to show their levels of active usage.
We developed a logging tool to track how many times participants created screenshots and reopened resources from Scrapbook{}.
We collected metadata and screenshots only if participants agreed to share this data, as their screenshots could have included personal information.
All participants shared complete metadata; \ADD{most of the participants shared the entire set of screenshots, while some shared a selection of screenshots.}
\ADD{Participants who declined to share some of their screenshots were concerned about the security of personal information captured in the screenshots.}
\ADD{The first author performed a thematic analysis and generated initial codes from the collected interview data.
Then, both authors discussed the codes and corresponding quotes iteratively until they fully agreed on the final result by revising, merging, and deleting the initial codes.}\marking{5}

\subsection{Descriptive Statistics for Scrapbook{} Usage}\marking{6}
During the one-week long field study, participants used Scrapbook{} to capture \ADD{212 screenshots in total, with }an average of 16.3 screenshots per user ($\sigma$ = 6.2, maximum = 32, minimum = 6).
\ADD{Out of all the screenshots, 62.3\% captured a single visible application window.}
The average number of visible windows per screenshot was 1.55 ($\sigma$ = 0.60, \ADD{maximum = 5}).
\ADD{Taking invisible windows into account, each participant selected and saved 3.13 ($\sigma$ = 1.94) windows on average per curation event.
This result shows that users added invisible windows alongside their visible windows.}
Most participants took both types of screenshot, with the exception of four who took only full-screen screenshots; 64.2\% of all captured screenshots were full-screen screenshots, and the rest were selected-area screenshots.
\ADD
Recorded computer activities and digital resources varied across individuals, from simple web surfing activity to complicated programming tasks.}
Participants' captures covered a wide range of applications, the majority being web browsers (63.5\%), followed by office software (7.6\%), PDF viewers (4.9\%), file managers (4.9\%), email applications (3.5\%), programming editors (2.7\%), and others.
\ADD{While the majority of screenshots featured web browsers, 26.2\% of screenshots contained only web browsers.
This result shows that existing bookmark functionality, which only covers web pages, would have been able to cover participants' needs to bundle various resources.}
On average, users opened applications from screenshots 0.78 times per day.
While this is below the average number of screenshots taken per day, it could have been the case that the need to reopen some resources did not occur during the study period.
Also, we later found out from our interviews that many participants simply took screenshots as visual reminders.
Overall, the descriptive statistics indicate that participants engaged with Scrapbook{} during the study, which allowed them to reflect on the user experience during the exit interviews.

\subsection{Recognition of Work at a Glance}

Participants found that using screenshots was effective in recognizing what a task was about at a glance.
Many participants (9/13) explicitly mentioned how easy it was to recognize the subject of a screenshot.
Here is one participant's comment that captures their perception of screenshot-based bookmarks:

\begin{quote}[P3]
``If I'm just looking at this [Collection View] for a second, like, you know, images grab your eye, and you might actually remember something and be like, `Oh, what is that?' Like \ldots So I think I'm more likely to remember. I think pictures are good because they jog your memory, like, pretty instantly. And you don't really have to write and they just catch your attention.''
\end{quote}

\noindent In particular, many participants (8/13) specifically mentioned how useful the Collection View was, perhaps even more often than the Detailed View, because they were able to quickly grasp their portfolio of resources at a glance.

\begin{quote}[P2]
(\textit{Responding to a follow-up question asking if user-supplied text, such as titles and descriptions, was helpful}) ``Um, for me, the screenshot was enough, because in the Collection View, I can already see every picture and just by, like, seeing that quick image of it, I know what it is. I did, like, put descriptions for all of mine, just, like, as an example to, like, say, what the specific part is about. But typically, I just look at the picture. I don't really look at the description part or the title part.''
\end{quote}

\noindent We realize that one of the critical values of Scrapbook{} is simply having a central repository for all screenshots.

\begin{figure*}[t]
  \centering
  \includegraphics[width=\textwidth]{sections/Images/screenshotexamples.png}
  \caption{Example screenshots from participants. Some parts of the images were redacted to protect participants' identities. Left: P10 captured multiple windows in the context of a job search for later task resumption. Middle: P1 captured a video that they wanted to revisit later. Right: P3 took a snapshot of their code for temporary version control.}
  \label{fig:code}
\end{figure*}
\subsection{Glanceable Bookmarks and To-do List}

In terms of the motivation behind taking screenshots, Scrapbook{} supported various participant needs.
Most participants (11/13) perceived the benefit of bookmark functionality; that is, being able to open resources from a screenshot.
Of the 13 participants interviewed, 10 mentioned that Scrapbook{} served as a cross-application bookmark manager that they used to curate multiple digital resources into bundles.
Other participants perceived a screenshot as a good way to keep track of tasks to complete (9/13). The following comments from P8 and P7 highlight how the Collection View helped them review their work.

\begin{quote}[P8]
``To keep a record for myself. And then, if later I want to reflect back on what I was doing on that day, I may be able to look at screenshots.''
\end{quote}
\begin{quote}[P7]
``I think Scrapbook{} is very good for reviewing the screenshots, because most oftentimes, when I screenshot something, I have to put it somewhere. And because it's in one place, I can search in it. Yeah, just wonderful. And I can have a title, and then searching the titles is very useful.''
\end{quote}

\noindent Some participants (3/13) used screenshots to increase their comfort with closing multiple applications.

In one interesting use case, a participant captured a screenshot of their code editor as a way to capture a version of their code before revising it (Figure~\ref{fig:code}-Right).
While the earlier version of the code would not have been available when opening the updated file from the screenshot, the screen captured one version that he believed it was stable.
Interestingly, the user was actually able to select and copy code text from the image using their web browser's built-in optical character recognition (OCR) functionality\footnote{\url{https://support.apple.com/guide/safari/interact-with-text-in-a-picture-ibrw20183ad7/mac}}, which fulfilled the purpose that the user intended.
\subsection{Specificity and Transiency}

One interesting trend we observed from our visual inspection of shared screenshots was that screenshots served more as short-term bookmarks that were useful to resume tasks or remind users of tasks to complete.
For example, one participant (P3) mentioned that they had a bookmark for the front page of a system in a web browser; the screenshot-based bookmark was linked to a specific page within the website.
The example the participant gave us was a learning management system (e.g., Canvas).
Using a traditional bookmark, they bookmarked the front page and had to then navigate the course website in multiple steps if they wanted to resume a grading task: expand the menu, select a course, choose a menu item, select an assignment, open a grader, and find the student they needed to resume grading from.
In contrast, the screenshot bookmark they created in Scrapbook{} was a link to a specific student's homework submission that they needed to resume grading from, resembling the original application of physical bookmarks: marking progress within a book, rather than merely marking the entire book.
Similar examples of specific bookmarks are also available in Figure~\ref{fig:code}-Left and -Middle).
P1, who took the screenshot in Figure~\ref{fig:code}-Middle, stated that they bookmarked the website before the study and ordinarily had to navigate from the front page to get to the video.
However, using Scrapbook{}, they bookmarked a page for a specific video they had been watching.
While it is not impossible to bookmark a specific page with a web browser's bookmark functionality, it seems that the temporally organized collection view with visual cues encouraged participants to create transient bookmarks for task resumption, as opposed to bookmarking gateways to specific resources.

\subsection{Concerns and Suggestions}

We asked if participants had any concerns or suggestions regarding Scrapbook{}.
While we explicitly mentioned that the system was a fully local application that does not communicate with other services, some participants (6/13) were concerned about personal information appearing in screenshots and wondered how much they could trust an app developer in practice.
There were many suggestions regarding the system. The most popular suggestion (6/13) was to add functionality for organizing screenshots.
Some participants suggested more traditional approaches, such as a hierarchical folder structure, even though we intentionally moved away from such approaches to minimize the effort expended to maintain such a hierarchy.
Others wanted more ways to filter out subsets of screenshots quickly, with tags and more powerful search functions.
One participant (P3) proposed that it would be excellent if Scrapbook{} could reproduce the window layout as well when restoring windows, which is feasible.
Another interesting suggestion was to store all the tabs in a web browser window.
We specifically avoided this functionality because it could capture too many tabs and overwhelm users with a long list of tabs in the Capture View.


\section{Introduction}
	\label{sec:intr}

	With the rise of artificial intelligence, robotics and autonomous systems are being designed to make complex decisions by reasoning about multiple goals at the same time.
	%
	Preference-based planning (PBP) allows the systems to decide which goals to satisfy when not all of them can be achieved \cite{hastie2010rational}.
	%
	Even though PBP has been studied since the early 1950's, most works on preference-based temporal planning (c.f. \cite{baier2008planning}) assume that all outcomes are pairwise comparable---that is, the preference relation is a \emph{total} order.
	%
	This assumption is strong and, in many cases, unrealistic\cite{aumann1962utility}.
	%
	In robotic applications, preferences may need to admit a \emph{partial} order because of (a) \emph{Inescapability}: An agent has to make decisions under time limits but with partial information about preferences because, for example, it lost communication with the server; and (b) \emph{Incommensurability}: Some situations, for instance, comparing the quality of an apple to that of banana, are fundamentally incomparable since they lack a standard basis to compare. These situations motivate the need for a planner that deals with partial order preferences in the presence of all uncertainties in its environment.

	\begin{figure}[h]
		\centering
		\includegraphics[width=1.0\linewidth]{figures/GapsGarden.png}
		\caption{
		 \textbf{a)} Bob's Garden.
		 \textbf{b)} Bob's preferences on how the bee robot perform the task of pollinating the flowers.
		}
		\label{fig:gap_garden}
	\end{figure}

	As a motivation example, consider Figure~\ref{fig:gap_garden}, which shows a garden that belongs to Bob. He grows three kinds of flowers: Tulips, daisies, and orchids. To pollinate the flowers, he uses a bee robot with limited battery. The environment is uncertain due to the presence of another agent (bird), the weather, and the robot dynamics.

    Bob has a preference for how the robot should achieve the task of pollination. Compared to the other types, tulips have a shorter life span, so Bob considers four outcomes

    \begin{itemize}
        \item[($p_1$)] pollinate tulips first, then at least one other flower type;
        \item[($p_2$)] pollinate two types of flowers, with the first being either daisies or orchids;
        \item[($p_3$)] pollinate only tulips; and
        \item[($p_4$)] at most one out of daisies and orchids is pollinated,
    \end{itemize}
    where the preference relation among them is shown in Figure~\ref{fig:gap_garden}b using a preference graph, where the nodes represent the outcomes, and each directed edge is an improving flip \cite{santhanamRepresentingReasoningQualitative2016}. Thus, $p_1$ is the most preferred and $p_4$ is the least preferred outcome, while $p_2$ and $p_3$ are incomparable with each other.
    %

    %
    As the robot has a limited battery life and the system is stochastic, it might not achieve the most preferred outcome with probability one.
    %
     Incomparable outcomes also introduce incomparable policies.

   Preference-based planning problems over temporal goals have been well-studied for deterministic planning given both total and partial preferences (see \cite{baier2008planning} for a survey). For preference specified over temporal goals, several works \cite{tumova2013least, wongpiromsarn2021, rahmani2020what} proposed minimum violation planning methods that decide which low-priority constraints should be violated in a deterministic system.
   %
   Mehdipour \emph{et al.}~\cite{mehdipourSpecifyingUserPreferences2021} associate weights with Boolean and temporal operators in signal temporal logic to specify the importance of satisfying the sub-formula and priority in the timing of satisfaction. This reduces the PBP problem to that of maximizing the weighted satisfaction in deterministic dynamical systems.

    However, the solutions to PBP problem for deterministic systems cannot be applied to stochastic systems.

    This is because in stochastic systems, even a deterministic policy yields a distribution over outcomes. Hence, to determine a better policy, we need comparison of distributions---a task a deterministic planner cannot do.

	Several works have studied the PBP problem for stochastic systems.
	%
	Lahijanian and Kwiatkowska~\cite{Lahijanian2016} considered the problem of revising a given specification to improve the probability of satisfaction of the specification. They

	formulated the problem as a multi-objective \ac{mdp} problem that trades off minimizing the cost of revision and maximizing the probability of satisfying the revised formula.
	%
	Li \emph{et al.}~\cite{li2020probabilistic} solve a preference-based probabilistic planning problem by reducing it to a multi-objective model checking problem.
	%
	However, all these works assume the preference relation to be \emph{total}.
	%
	To the best of our knowledge, \cite{fu2021probabilistic} is the only work that studies the problem of probabilistic planning with incomplete preferences.
	%
	The authors introduce the notion of the value of preference satisfaction for planning within a pre-defined finite time duration and developed a mixed-integer linear program to maximize the satisfaction value for a subset of preference relations. In comparison, our work resorts to the notion of stochastic ordering to compare policies in the stochastic system with respect to the partial order of temporal goals and allows the time horizon to be finite, but unbounded.

	To conclude, our contributions in this paper are three-fold: (1) We introduce a new computational model called a \emph{Preference Deterministic Finite Automaton (PDFA)}. A PDFA can model a user's (possibly partial) preferences over temporally extended goals; (2) We identify the connection between the PBP problem in probabilistic planning and stochastic orders \cite{masseyStochasticOrderingsMarkov1987}. This allows us to reduce the problem of probabilistic planning with partial preferences over temporal goals to that of finding the set of weak-stochastic nondominated policies in a product of \ac{mdp} and the PDFA. (3) We employ the property of weak-stochastic nondominated policies to design multiple objectives in the product \ac{mdp} and prove that a Pareto-optimal policy in the resulting multi-objective product \ac{mdp} is weak-stochastic nondominated respecting the preference relation. Thus,
	the set of weak-stochastic nondominated policies can, then, be computed using any off-the-shelf solver that computes Pareto optimal policies in polynomial time.

	\section{Preliminaries and Problem Formulation}
	\label{sec:def}
	%

	\textbf{Notations} The set of all finite words over a finite alphabet $\Sigma$ is denoted $\Sigma^\ast$. The empty string $\Sigma^0$ is denoted as $\epsilon$. The set of all probability distributions over a finite set $X$ is denoted $\mathcal{D}(X)$.
	%
    Given a distribution $\mathbf{d}\in \mathcal{D}(X)$, the probability of an outcome $x\in X$ is denoted $\mathbf{d}(x)$. %

	\subsection{The System and its Policy}
	%

    We model the system using a variant of MDP.

	\begin{definition}
		\label{def:labeled_mdp}
		A \ac{tlmdp}, or a terminating MDP for short, is a tuple  $M = \langle S, A:=\bigcup_{s \in S} A_s, \mathbf{P}, s_0, s_\bot, \mathcal{AP}, L \rangle$ in which
		$S$ is a finite set of states;
		%
		$A$ is a finite set of actions, where for each state $s \in S$, $A_s$ is the set of available actions at $s$;
		%
		$\mathbf{P}: S \times A   \rightarrow \mathcal{D}(S)$ is the probabilistic transition  function, where for each $s, s' \in S$ and $a \in A$, $\mathbf{P}(s, a, s')$ is the probability that the MDP transitions to $s'$ after taking action $a$ at $s$;
		%
		$s_0 \in S$ is the initial state;
		%

		%
		$s_\bot \in S$ is the \emph{termination state}, which is a unique \emph{sink} state and $A_{s_\bot} = \emptyset$;
		%
		$\mathcal{AP}$ is a finite set of atomic propositions; and
		%
		$L: S \rightarrow 2^{\mathcal{AP}} \cup \{\epsilon\}$ is a labeling function that assigns to each state $s\in S \setminus \{s_\bot\}$, the set of atomic propositions $L(s) \subseteq \mathcal{AP} $ that hold in $s$.
		Only the terminating state is labeled the empty string, i.e., $L(s)=\epsilon$ iff $s=s_\bot$
	\end{definition}
	%

	Though this definition assumes a single sink state, we do not lose generality, as one can always convert any MDP with more than one sink state into an equivalent MDP that has only a single sink state by redirecting proper transitions to that sink state. \gobble{,by keeping one of those states to be the termination state and adding transitions for $a_\bot$ from all other sink states to that termination state.}

	The robot's interaction with the environment in a finite number $k$  of steps produces an \emph{execution} $\varrho = s_0 a_0 s_1 a_1 \cdots s_{k-1} a_{k-1} s_{k}$, where $s_0$ is the initial state and at each step $0 \leq i \leq k$, the system is at state $s_i$, the robot performs $a_i \in A_{s_i}$, and then the system transitions to state $s_{i+1}$, picked randomly based on $\mathbf{P}$ among those states for which $\mathbf{P}(s_i, a_i, .) > 0$.
	%
	This execution produces a \emph{path} defined as $\rho=s_0 s_1 \cdots s_k \in S^*$,
	and the \emph{trace} of this path is defined as the finite word $\operatorname{trace}(\rho)=L(s_0) L(s_1) L(s_2) \cdots L(s_k)  \in (2^\mathcal{AP})^*$.
	%

	%
	Path $\rho$ is called \emph{terminating} if $s_k = s_\bot$.
	%
	The set of all terminating paths in $M$ is denoted $\operatorname{Paths}_{\bot}(M)$.

 	\gobble{Note that we might forbid the robot to terminate its execution in a certain state, by not allowing that state to have an action that reaches the termination state with some positive probability.}

    A policy for $M$ is a function $\pi: \textsc{Dom} \rightarrow \textsc{CoDom}$ where it is called \emph{memoryless} if $\textsc{Dom}=S$; \emph{finite-memory} if $\textsc{Dom}=S^*$; \emph{deterministic} if $\textsc{CoDom}=A$, and \emph{randomized} if $\textsc{CoDom}=\mathcal{D}(A)$.
	%

	%

	%
In a terminating \ac{mdp}, a policy is \emph{proper} if it guarantees that the termination state $s_\bot$ will be reached with probability one \cite{bertsekas1991analysis}. 	The set of all randomized, finite-memory, proper polices for $M$ is denoted $\Pi_{prop}^M$. We  are  only interested in  finite traces for which a preference relation is defined. Thus, we only consider proper policies.
	%
	%
	\begin{assumption}
	  We assume all the policies for the MDP are proper.
	\end{assumption}
	In this paper, we consider only the MDPs for which all the policies are proper.
	%
	We consider applications where the robot finishes its execution in a finite time, and in fact, in many robotics application, the robot has a battery limit or a limited lifespan and cannot execute forever.
	%
	%
	%

	%

	%

	%
	\subsection{Rank the policies}
	%

	We introduce a computational model that captures the user's preference over different temporal goals. \gobble{the robot can achieve in the environment.}
	%
	\begin{definition}
		\label{def:model_preference}
		Given a countable set $U$, a \emph{preference model} for $U$, denoted $\succeq^U$

		is a partial order over the elements of $U$.
	\end{definition}
	We simply use  $\succeq$ for $\succeq^U$ if its meaning is clear
		from the context.
     Given $u_1, u_2 \in U$, we write $u_1 \succeq u_2$ if $u_1$ is \emph{weakly preferred to} (i.e.,  is at least as good as) $u_2$; and $u_1\sim u_2$ if $u_1\succeq u_2$ and $u_2\succeq u_1$,
    that is,  $u_1$ and $u_2$ are \emph{indifferent}.
    We write
    $u_1 \succ u_2$ to mean that $u_1$ is \emph{strictly preferred} to $u_2$, i.e., $u_1\succeq u_2$ and $u_1\not \sim u_2$.  We write
	$u_1 \nparallel u_2$ if $u_1$ and $u_2$ are \emph{incomparable}.
	%
		\begin{definition}\cite{masseyStochasticOrderingsMarkov1987}. Given a countable set $U$ partially ordered by a preference model $\succeq$, the \emph{weak-stochastic ordering} for $U$ is denoted $\mathfrak{E}_{wk}(U)$ and is defined as the family of subsets

		   \begin{equation}
		       \mathfrak{E}_{wk}(U) =\bigcup_{x\in U} \{x\}^\uparrow \cup \{U, \emptyset\}.
		   \end{equation}
		   where $\{x\}^\uparrow =\{y \mid y \succeq x \}$ contains all elements in $U$ that are at least as good as $x$, according to the partial order $\succeq$.
		\end{definition}

        The weak-stochastic ordering for $U$ allows us to rank different probability measures on $U$.
        %
        Given two probability measures $P_1$ and $P_2$ on $U$, we say $P_1$ \emph{weak-stochastic dominates} $P_2$ under $\succeq$, denoted $P_1 >_{\mathfrak{E}_{wk}} P_2$,
        if $P_1[X] \geq P_2[X]$ for each $X \in \mathfrak{E}_{wk}(U)$ and $P_1[Y] > P_2[Y]$ for some $Y \in \mathfrak{E}_{wk}(U)$. Intuitively, for any  outcome  $x$ in $U$, the probability of getting an outcome (weakly) preferred to $x$ in $P_1$ is at least as good as that in $P_2$, and for some outcome $x'\in U$, the probability of getting an outcome preferred to $x'$ in $P_1$ is higher than that in $P_2$.
        %

        To illustrate, consider the following example.
        %
     \begin{example}
	 	Let $U = \{a,b,c,d\}$ and  $\succeq = \{(a, b), (b, d), (c, d), (a, c), (a, d) \}$, where $(x,y)\in \succeq$ if and only if $x\succeq y$.
	 	%
	 	We have
	 		\[
	 	\mathfrak{E}_{wk}(U) = \{ \{a\}, \{a,b\}, \{a,c\}, \{a,b,c,d\}, \emptyset\}.
	 	\]
        %
	 	Now consider three probability measures $P_1$, $P_2$, and $P_3$ where $P_1(a)=P_1(b)= 0.5$, $P_2(a) =P_2(c) = 0.5$, and $P_3(a) =P_3(d) = 0.5$.
	 	%
	 	Accordingly,
	 	\[
	 	[P_1[X]]_{X\in	\mathfrak{E}_{wk}(U) }= [0.5, 1, 0.5, 1, 0],
	 	\]
	 	\vspace{-18pt}
	 	\[
	    [P_2[X]]_{X\in	\mathfrak{E}_{wk}(U) }= [0.5, 0.5, 1, 1, 0], \text{and}
	 	\]
	 	\vspace{-18pt}
	 	\[
	 	[P_3[X]]_{X\in 	\mathfrak{E}_{wk}(U) }   = [0.5, 0.5, 0.5, 1, 0].
	 	\]
	 	%
	 	Therefore, $P_1 >_{\mathfrak{E}_{wk}} P_3$, $P_2 >_{\mathfrak{E}_{wk}} P_3$. None of $P_1$ and $P_2$ weak-stochastic dominates the other one.
        %
    \end{example}
	%
	%
    %

	In this context,
	the user preference over temporal goals is a preference model for $U=\Sigma^*$ where $\Sigma= 2^\mathcal{AP}$. Based on the ranking of probability measures induced by the weak-stochastic ordering for $\Sigma^\ast$, we can rank the proper policies $\Pi^M_{prop}$ in the \ac{tlmdp} as follows.

	Note that a proper policy $\pi: S^\ast \rightarrow \mathcal{D}(A)$ produces a distribution
	over the set of all terminating paths in the MDP $M$ such that for each terminating path $\rho \in \operatorname{Paths}_{\bot}(M)$,

	$\Pr^\pi(\rho)$
	is the probability of generating $\rho$ when the robot uses policy $\pi$.
		%
	    Each terminating path $\rho$ is mapped to a single word in $\Sigma^*$, namely $\operatorname{trace}(\rho)$,
		%
		and therefore, $\pi$ yields a distribution
		over the set of all finite words over $\Sigma$\gobble{---the alphabet of the preference DFA}
		such that for each word $w \in \Sigma^\ast$, $\Pr^\pi(w)$ is the probability that
		$\pi$ produces $w$.
		%

  %
\begin{definition}
\label{def:weak_dominating_policies}
         Given two proper policies $\pi,\pi'$ in the terminating labeled \ac{mdp} $M$, $\pi$ \emph{weak-stochastic dominates} $\pi'$, denoted $\pi >_{\mathfrak{E}_{wk}} \pi'$, if for each $w \in \Sigma^\ast$, it holds
         that $\Pr^{\pi}(\{w\}^\uparrow) \ge \Pr^{\pi'}(\{w\}^\uparrow)$, and there exists a word $w' \in \Sigma^\ast$ such that
         $\Pr^{\pi}(\{w'\}^\uparrow) > \Pr^{\pi'}(\{w'\}^\uparrow)$.
\end{definition}

This definition is used to introduce the following notion.

	\begin{definition}
		\label{def:sto_dominance}
		   A proper policy $\pi \in \Pi_{prop}^M$ is \emph{weak-stochastic nondominated} if there \emph{does not exist} any policy $\pi' \in \Pi_{prop}^M$ such that $\pi' >_{\mathfrak{E}_{wk}}\pi$.
	\end{definition}

Informally, we say a policy $\pi$ is \emph{preferred}, if and only if it is weak-stochastic nondominated in $\Pi_{prop}^M$.

	Next, we state our problem informally.
	\begin{problem}
	    Given a terminating labeled \ac{mdp} and a preference model $\succeq$ over finite words $\Sigma^\ast$, compute a proper policy that is weak-stochastic nondominated.
	\end{problem}
		%

		\section{Main results}

		%
	    \subsection{Preference Deterministic Finite Automaton}
		%
	%
	 In this section, we propose a finite automaton to compatibly represent the user preferences over temporal goals.
	 %

	%

	%

	%

	\begin{definition}
		\label{def:pdfa}
		A \ac{pdfa} for an alphabet $\Sigma$ is a tuple $\mathcal{A}= \langle Q, \Sigma, \delta, {\iota}, G:=(\mathbb{F}, E) \rangle$
		in which $Q$ is a finite set of states;
		%
		$\Sigma$ is the alphabet;
		%
		$\delta: Q \times \Sigma \rightarrow Q$ is the transition function;
		%
		${\iota} \in Q$ is the initial state;
		%
		and $G=(\mathbb{F}, E)$ is a \emph{preference graph} in which,
		$\mathbb{F} = \lbrace F_1, F_2, \cdots, F_m \rbrace$ is a partition of $Q$---i.e.,
		    $F \subseteq Q$ for each $F \in \mathbb{F}$, $F \cap F' = \emptyset$ for each distinct state subsets
		     $F, F' \in \mathbb{F}$, and $\bigcup_{F \in \mathbb{F}} F = Q$; and $E \subseteq \mathbb{F} \times \mathbb{F}$ is a set of directed edges

		%
		\end{definition}
		%
		With a slight abuse of notation, we define the extended transition function $\delta: Q \times \Sigma^\ast \rightarrow Q$ in the usual way, i.e., $\delta(q,\sigma w) = \delta(\delta(q,\sigma), w)$ for $w\in \Sigma^\ast$ and $\sigma \in \Sigma$, and $\delta(q, \epsilon)=q$.
		%
		Note that Definition~\ref{def:pdfa} augments the classical deterministic finite automaton~\cite{hopcroft2001introduction} with the preference graph $G$, instead of a set of accepting (final) states.
		%

		%
		%

		For two vertices $F, F' \in \mathbb{F}$, we write $F  \rightsquigarrow F'$ to denote $F'$ is \emph{reachable} from $F$.
		%
		By convention, each vertex $F$ of $G$ is reachable from itself. That is, $F\rightsquigarrow F$ always holds.
		%
		%

		The \ac{pdfa} encodes a preference model $\succeq$ for $\Sigma=(2^\mathcal{AP})^*$ as follows.
		%
		Consider two words $w, w' \in \Sigma^*$.
		%
		Let $F, F' \in \mathbb{F}$ be the two state subsets such that $\delta(q, w) \in F $ and $\delta(q, w') \in F'$ (recall that $\mathbb{F}$ is a partitioning of $F$);
		There are four cases: (1) if $F  = F'$, then $w \sim w'$; (2) if $F  \neq F'$ and $F' \rightsquigarrow F $, then $w \succ w'$; (3) if $F  \neq F' $ and $F \rightsquigarrow F'$, then $w' \succ w$; and (4) otherwise, $w \nparallel w'$.

		%

	    To illustrate, see Figure~\ref{fig:pdfa}, which shows a preference DFA specifying the preferences in the example of Figure~\ref{fig:gap_garden}.
	    %
	    State subsets $F_1 = \{q_2\}$, $F_2=\{q_4\}$, $F_3 = \{q_1\}$, and $F_4 = \{q_0, q_3, q_5\}$ respectively represent preferences $p_1$ through $p_4$.
	    %

	\gobble{For a state subset  $F_1 \in \mathbb{F}$, all the finite words that reach those states within $F_1$ are indifferent to one another, and for each pair of state subsets $F_1, F_2 \in \mathbb{F}$ for which there is a path from $F_2$ to $F_1$ in $\mathcal{G}$, all words reaching a state within $F_1$ are preferred over any word reaching a state within $F_2$. If there is no path between two distinct state subsets $F_1$ and $F_2$, than any word that reaches a state within $F_1$ is incomparable to any word that reaches a state within $F_2$.}
	%

			\begin{figure}[h]
		\centering
		\includegraphics[width=1.0\linewidth]{figures/PDFA.png}
		\caption{
		 PDFA for the example in Figure~\ref{fig:gap_garden}.
		 %
		 \textbf{Left)} The DFA structure of PDFA.
		 %
		 \textbf{Right)} The preference graph of PDFA.
		 %
		}
		\label{fig:pdfa}
	\end{figure}

	The following Lemma allows us to define the weak-stochastic ordering over $\Sigma^\ast$, defined by the \ac{pdfa}, using its preference graph.

	\begin{lemma}
	\label{lem:wUp}
	For each word $w\in \Sigma^\ast$, if $\delta({\iota}, w)\in F$ for some $F\in \mathbb{F}$, then
	 \begin{multline}

	 	\{ w\}^\uparrow = \{w' \in \Sigma^\ast \mid \exists F' \in \mathbb{F},\\ \delta({\iota}, w')  \in F' \text{ and } F\rightsquigarrow F'\}
	\end{multline}
\end{lemma}
The lemma directly follows from the transitivity property in the transition function in $\mathcal{A}$ and the preference relation and thus
the proof is omitted.
	%

    %

    %
    %

            \problembox{Probabilistic Planning with Partially Ordered Preferences ({\rm PPwPOP}\xspace)}
{A \ac{tlmdp} $M = \langle S, A:=\Sigma_{s \in S}A_s, \mathbf{P}, s_0, s_\bot, \mathcal{AP}, L \rangle$ and a \ac{pdfa} $\mathcal{A}= \langle Q, 2^\mathcal{AP}, \delta, {\iota}, G := (\mathbb{F}, E) \rangle$.}
{The set of all proper polices for $M$ that are weak-stochastic nondominated under the preferences specified by $\mathcal{A}$.
}

	\section{Synthesizing a preferred policy}
	\label{sec:alg}
	%
	We now present our algorithm\gobble{ to solve {\rm PPwPOP}\xspace}.
	%
The first step is to augment the planning state space with the state of the \ac{pdfa}.
With this augmented state space, we can relate the preferences over traces in the \ac{mdp} to a preference over subsets of terminating states in a product \ac{mdp} we define as follows.
	\begin{definition}[Product MDP]
	\label{def:prod}
	Let $M = \langle S, A:=\Sigma_{s \in S}A_s, \mathbf{P}, s_0, s_\bot, \mathcal{AP}, L \rangle$ and
	 $\mathcal{A} = \langle Q, \Sigma, \delta, {\iota}, G:=(\mathbb{F}, E) \rangle$ be respectively the \ac{tlmdp} and the \ac{pdfa}. The product of $M$ and $\mathcal{A}$ is a tuple 	$\mathcal{M} = (X, A:=\bigcup_{x \in X}A_x, \mathbf{T}, x_0, X_G, \mathcal{G} := (\mathcal{W}, \mathcal{E}))$ in which
	\begin{enumerate}
	    \item $X =  S \times Q$ is the state space;
	    \item $A$ is the action space, where for each $x=(s, q) \in X$, $A_x = A_s$ is the set of available actions at state $x$;
	    \item \label{itm:T} $\mathbf{T}: X \times A \times X \rightarrow [0, 1]$ is the transition function such that for each state $(s, q) \in X$, action $a \in A$, and state $(s', q') \in X$;
	    \begin{multline*}
     \mathbf{T}((s, q), a, (s', q')) = \\  {
    \begin{cases}
        \mathbf{P}(s, a, s') & \mbox{\text{if} $q' = \delta(q, L(s')),$} \qquad\hfill (\ref{itm:T}.a) \\
        0 & \text{otherwise};
    \end{cases}
    }
\end{multline*}
	    \item $x_0 = (s_0, \delta({\iota}, L(s_0)))$ is the initial state;
	    \item $X_G =  \{s_\bot \} \times Q$ is the set of terminating states;
	    \item \label{itm:pgraph} $\mathcal{G} = (\mathcal{W}, \mathcal{E})$ is the preference graph, in which, letting $W_i = \{s_\bot\}\times F_i$ for each $F_i \in \mathbb{F}$,
	    \begin{itemize}
	        \item $\mathcal{W} = \{W_i\mid i=1,\ldots, \abs{\mathbb{F}}\}$ is the vertex set of the graph, and
	        \item $\mathcal{E}$ is the edge set of the graph such that $(W_i, W_j)\in \mathcal{E}$ if and only if $(F_i, F_j ) \in E$.
	    \end{itemize}
	    \end{enumerate}
	\end{definition}
	%
	%

	The preference graph of this MDP has been directly lifted from the one defined for the \ac{pdfa}. We use $W \rightsquigarrow W'$ to denote
	 that $W'$ is reachable from $W$ in the preference graph $\mathcal{G}$. Again, every $W$ is reachable from itself.
	%

    Continuing with the example in Figure~\ref{fig:pdfa}, we have $W_1 = \{ s_\bot\} \times F_1 = \{(s_\bot, q_2)\}$, $W_2 =\{s_\bot\} \times  F_2=\{(s_\bot, q_4)\}$, $W_3 = \{s_\bot \} \times F_3 = \{(s_\bot, q_1)\}$, and $W_4 = \{s_\bot\} \times F_4 = \{(s_\bot, q_0), (s_\bot, q_3), (s_\bot, q_5)\}$.

	%
    %

	%

    %

    %

	%

    %

    %

      	\normalcolor

    %

    %
   Next, we show how to compute a weak-stochastic nondominated policy, in the sense of Definition~\ref{def:sto_dominance}, through solving a multi-objective \ac{mdp}.

     Given the product MDP $\mathcal{M}$ constructed
		   in Definition~\ref{def:prod}, the \emph{weak-stochastic ordering} for
		   $\mathcal{W}$, denoted $\mathfrak{E}_{wk}(\mathcal{W})$, is the family of subsets

		\begin{equation}
	   	    \mathfrak{E}_{wk}(\mathcal{W}) =  \{\{W\}^\uparrow \mid W\in \mathcal{W} \}  \cup \{ \emptyset, \mathcal{W} \}
	   \end{equation}
        where $\{W\}^\uparrow = \bigcup_{W'\in \mathcal{W}, W\rightsquigarrow W'} \{W'\}$.

    %

Note that by construction, the number of subsets
in $\mathfrak{E}_{wk}(\mathcal{W})$ minus the empty set and the set $\mathcal{W}$ is exactly the size of $\mathcal{W}$.
Let $N = \abs{\mathcal{W}}$.
    %
    \begin{definition}[\ac{momdp}]
	\label{def:goalMDP}
	The multi-objective MDP (MOMDP) associated with the product MDP $\mathcal{M} = \langle X, A, \mathbf{T}, x_0, X_G, \mathcal{G} := (\mathcal{W}, \mathcal{E}) \rangle$ in Definition~\ref{def:prod} is a tuple $\mathcal{P} = \langle X, A:=\bigcup_{x \in X}A_x, \mathbf{T}, x_0, X_G, \mathcal{Z}=\{Z_1, Z_2, \cdots, Z_N \} \rangle$ in which $X$, $A$, $\mathbf{T}$, $x_0$, and $X_G$ are  the same elements in $\mathcal{M}$ and for each $i \in \{1, \cdots, N\}$, $Z_i = \bigcup_{W \in \{W_i\}^\uparrow} W$.
	%
	The $i$-th objective in the \ac{momdp} is to maximize the probability for reaching the set $Z_i$.
	\end{definition}
    %

    Note that each $Z_i$ is a subset of goal states $X_G$, and that
    the intersection of two distinct goal subsets $Z_i$ and $Z_j$ may not be empty.

    Using the
running  example in Figure~\ref{fig:pdfa}, we have $\{W_1\}^\uparrow = \{W_1\}$, $\{W_2\}^\uparrow = \{W_1, W_2\}$,
    $\{W_3\}^\uparrow = \{W_1, W_3\}$, and $\{W_4\}^\uparrow = \{W_1, W_2, W_3, W_4\}$; $Z_1= W_1$, $Z_2= W_1\cup W_2$, $Z_3= W_1\cup W_3$, and $Z_4 = \bigcup_{i=1}^4 W_i$.

    %

    %

    %

    %

    In this \ac{momdp}, for a given randomized, finite-memory policy $\mu: X^* \rightarrow \mathcal{D}(A)$, we can compute the value vector of $\mu$ as a $N$-dimensional vector $\mathbf{V}^\mu=[\mathbf{V}_1^\mu, \mathbf{V}_2^\mu, \cdots, \mathbf{V}_N^\mu]$ where for each $i$, $\mathbf{V}_i^\mu$ is the
    probability of reaching states of $Z_i$ by following policy $\mu$, starting from the initial state.

    Given a randomized, memoryless policy $\mu: X \rightarrow \mathcal{D}(A)$, to compute its value vector $\mathbf{V}^\mu$, we first set for each goal state $x_g \in X_G$, $\mathbf{V}^\mu(x_g)$ to be the vector such that for each $i \in \{1, \cdots, n \}$, $\mathbf{V}^\mu_i(x_g) = 1$ if $x_g \in Z_i$, and otherwise $\mathbf{V}^\mu_i(x_g) = 0$. Then we compute the values of the non-goals states $x \in X \setminus X_G$ via the Bellman recurrence
    %
    \begin{equation}
        \mathbf{V}^{\mu}(x) = \sum_{a \in A} \left ( \mu(x)[a] \sum_{x' \in X} \mathbf{T}(x, a, x') \mathbf{V}^{\mu}(x') \right ).
    \end{equation}
    %

    %

    %
    \begin{definition}
    \label{def:paretoDomPolicy}
               Given two proper polices $\mu$ and $\mu'$ for $\mathcal{M}$, it is said that $\mu$ \emph{Pareto dominates} $\mu'$,
               denoted $\mu > \mu'$, if for each $i \in \{1, \cdots, N\}$, $\mathbf{V}_i^{\mu} \geq \mathbf{V}_i^{\mu'}$, and for at least one $j \in \{1, \cdots, n\}$, $\mathbf{V}_j^{\mu} > \mathbf{V}_j^{\mu'}$.
    \end{definition}
    %
    Intuitively, $\mu$ Pareto dominates $\mu'$ if, compared to $\mu'$, it increases the probability of reaching at least a set $Z_i$ without reducing the probability of reaching other sets $Z_j$'s.
    %

    %
    \begin{definition}
  \label{def:nonDomPolicy}
             A proper policy $\mu$ for the MOMDP in Definition~\ref{def:goalMDP} is \emph{Pareto optimal} if for no proper policy $\mu'$ for the MOMDP it holds that $\mu' > \mu$.
    \end{definition}
    In other words, a policy is Pareto optimal if it is not dominated by any policy.
     %
   The \emph{Pareto front} is the set of all Pareto optimal policies.
    %
     It is well-known that the set of memoryless policies suffices for achieving the Pareto front ~\cite{chatterjee2006markov}. Thus, we restrict to compute memoryless policies.
     %
     %

     %

    %

    With this in mind, we present the following result.
    %
    \begin{theorem}
    \label{thm:pareto-weakstochastic}
        Let $\mu: X \rightarrow \mathcal{D}(A)$ be a policy for $\mathcal{P}$.
        %
        Construct policy $\pi: S^* \rightarrow \mathcal{D}(A)$ for the \ac{tlmdp} $M$ such that for each $\rho=s_0 s_1 \cdots s_n \in S^*$ it is set
        $\pi(\rho) = \mu(s_n, \operatorname{trace}(\rho))$.
        %
        If $\mu$ is Pareto optimal, then $\pi$ is weakly-stochastic nondominated, respecting the preference specified by \ac{pdfa} $\mathcal{A}$.
    \end{theorem}
    %
    \begin{proof}

    We show that if $\mu$ is Pareto optimal then $\pi$ is weak-stochastic nondominated. To facilitate the proof, the following notation is used: Let $\Pr^\mu(\mbox{reach}(X), \mathcal{M})$ be the probability of terminating in the set $X$ given the policy $\mu$ for the MOMDP and $\Pr^\pi(\mbox{reach}(X), M)$ be the probability of terminating in the set $X$ given the policy $\pi$ in the original  \ac{tlmdp}.

    First, consider that by the construction of the product MDP, Definition~\ref{def:prod}, preference graphs $\mathcal{G}$ and $G$ are isomorphic, and thus, each $W_i \in \mathcal{W}$ is mapped to a single $F_i \in \mathbb{F}$, and vice versa.
    %
    Let's define $F_i^+ =\bigcup_{F, F_i \rightsquigarrow F} F$ for each $F_i \in \mathbb{F}$.
    %
    Given that $\mathcal{G}$ and $G$ are isomorphic, $W_i \rightsquigarrow W_j$ if and only if $F_i \rightsquigarrow F_j$ for all $i, j \in \{1, 2, \cdots, N \}$.

    This combined with that $Z_i = \bigcup_{W \in \{W_i\}^\uparrow} W$ for $i \in \{1, \cdots, N\}$ by Definition~\ref{def:goalMDP}, implies that for each $i$,
    %
    \begin{equation}
    \label{eq:Zi_Fi}
       \mathbf{V}_i^\mu =  \Pr^\mu(\reach{Z_i}, \mathcal{M}) = \Pr^\pi(\mbox{reach}(F_i^+) , M\}.
    \end{equation}

    %
    Next, for each $w, w' \in \Sigma^\ast$ such that $\delta({\iota}, w)=\delta({\iota}, w')$, it holds that $\{w\}^\uparrow = \{w'\}^\uparrow$.
    %
    Given this and Lemma~\ref{lem:wUp}, for each $F_i$ and $w \in \Sigma^\ast$ such that $\delta({\iota}, w) \in F_i$,
    %
    \begin{equation}
    \label{eq:Fi_W}
        \Pr^\pi(\mbox{reach}(F_i^+), M) =\Pr^\pi(\{w\}^\uparrow ).
    \end{equation}

    Finally, given that $\mu$ is a Pareto optimal policy, by Definition~\ref{def:paretoDomPolicy} and Definition~\ref{def:nonDomPolicy}, it means there exists no policy $\mu'$ such that
     $\mathbf{V}_i^{\mu'} \geq \mathbf{V}_i^\mu$ for all integers $1 \leq i \leq n$ and
    $\mathbf{V}_j^{\mu'} > \mathbf{V}_j^\mu$ for some integer $1 \leq j \leq n$.
    %
    This, by (\ref{eq:Zi_Fi}) and (\ref{eq:Fi_W}) and that the set of randomized, memoryless policies suffices for the Pareto front of $\mathcal{M}$, means there exists no policy $\pi' \in \Pi^M_{prop}$ such that $\Pr^{\pi'}(\{w\}^\uparrow ) \geq \Pr^{\pi}(\{w\}^\uparrow )$ for every $w \in \Sigma^*$ and  $\Pr^{\pi'}(\{w'\}^\uparrow ) > \Pr^{\pi}(\{w'\}^\uparrow )$ for some $w' \in  \Sigma^*$.
    %
    This, by Definition~\ref{def:weak_dominating_policies} and Definition~\ref{def:sto_dominance}, means that $\pi$ is weak-stochastic nondominated.

    \end{proof}

    Now one can use any existing methods to compute a set of Pareto optimal policies for $\mathcal{P}$.
    %
    For a survey of those methods, see~\cite{roijers2013survey}.
    %
    Note that computing the set of all Pareto optimal policies is generally infeasible, and thus, one needs to compute only a subset of them or to approximate them.
    %

    \section{Case Study: Garden}

    %

    %

    In this section, we present the results from the planning algorithm for the running example in Figure~\ref{fig:gap_garden} .
    %

    %

    %

    %
In the garden, the actions of the robot are $N$, $S$, $E$, $W$---for receptively moving to the cell in the North, South, East, and West side of the current cell---and $T$ for staying in the current cell. The bee robot initially has a full charge, and using that charge it can fly only $12$ time steps.

\noindent \textbf{Uncertain environment: } A bird roams about  the south east part of the garden, colored yellow in the figure.
    %
    When the bird and the bee are within the same cell, the bee needs to stop flying and hide in its current location until the bird goes away. The motion of the bird is given by a Markov chain.

    %

    %

    %

    Besides the stochastic movement of the bird,
the weather is also stochastic and affects the robot's planning.
    %
    The robot cannot pollinate a flower while raining.
    %
    We assume when the robot starts its task, at the leftmost cell at the bottom row, it is not raining and the probability that it will rain in the next step is $0.2$.
    %
    This probability increases for the consecutive steps each time by $0.2$ until the rain starts.

    %

    %
    Once the rain started, the probability for the rain to stop in the five following time steps will respectively be $0.2$, $0.4$, $0.6$, $0.8$, and $1.0$, assuming the rain has not already stopped at any of those time steps.
    %
    %

    %

	We implemented this case study in Python and considered two variants of it, one without stochasticity  in the robot's dynamics, and one with stochasticity.
	%
	In the former case, when the robot decides to perform an action to move to a neighboring cell, its actuators will guarantee with full certainty that the robot will move to that cell after performing the action.
	%
	In the later case, the probability that the robot reaches the intended cell is $0.7$, and for each of the unintended directions except the opposite direction, the probably that the robot's actuators move the robot to that unintended direction is $0.1$. If the robot hits the boundary, it stays in its current cell.

	All the experiments were performed on a Windows 11 installed on a device with a core i$7$, 2.80GHz CPU and a 16GB memory.

	\subsection{Deterministic Robot in the Uncertain Environment}
	%

	%
	The MDP for this case has $10,460$ states and $280,643$ transitions (its transition function has $280,643$ entries with non-zero probabilities).
	%
	It took $47.38$ seconds for our program to construct the MDP.
	%
	The product MDP had $36,649$ states and $946,467$ transitions.
	%
	The construction time for the product MDP was $408.87$ seconds.
	%

	%

	 Given the preference described in Fig.~\ref{fig:pdfa}, we employ linear scalarization methods to solve the \ac{momdp}.
    %

Specifically,    given a    weight vector $\mathbf{w}=[w_1, w_2, w_3, w_4]$, we compute the weak-stochastic nondominated policy $\mu_{\mathbf{w}}$, by first setting $V_{\mathbf{w}}(x) = \sum_{i: x \in Z_i} w_i$ for each goal state $x \in X_G$, and then by solving the following Bellman equation for the values of  the non-goal states
    %
    \begin{equation}
        V_{\mathbf{w}}(x) = \max_{a \in A_x} \sum_{x' \in X} \mathbf{T}(x, a, x')V_{\mathbf{w}}(x'), \forall x \in X \setminus X_G.
    \end{equation}
    %

    The policy is recovered from $ V_{\mathbf{w}}(x)$ as
    \begin{equation}
        \mu_{\mathbf{w}}(x) = \mathop{\mathrm{argmax}}_{a \in A_x} \sum_{x' \in X} \mathbf{T}(x, a, x')V_{\mathbf{w}}(x'), \forall x\in X \setminus X_G.
    \end{equation}

 	We randomly generated $100$ weight vectors and used each one of them to compute a Pareto optimal policy for the MOMDP.  The computed Pareto-optimal policies in the \ac{momdp} yield  a  set of $100$ weak-stochastic nondominated policies.
	%

	%
   From the result, it is noted that none of those computed polices were weak-stochastic dominated by the other polices. This is expected due to Theorem~\ref{thm:pareto-weakstochastic}.
    %

    %

    %

    %
    Table~\ref{tbl:nondom_policies} shows $10$ out of those $100$ weight vectors along with the value vectors of the polices computed for those weight vectors and the corresponding probabilities those polices assign to the four preferences $p_1$ through $p_4$.

    %
        	    \begin{table}[h!]
	    \setlength{\tabcolsep}{0.2em}
    \centering
    \begin{tabular}{cccc}
    \hline \hline
     & \scriptsize     Weight Vector & \scriptsize  Value Vector & \scriptsize  Prob. of individual outcomes \\

    \hline

   \scriptsize 1 &  \scriptsize [0.50, 0.17, 0.21, 0.12] & \scriptsize 	[0.24, 0.25, 0.98, 1.0] & \scriptsize [0.24, 0.01, 0.74, 0.01] \\

   \scriptsize 2 &  \scriptsize [0.08, 0.46, 0.38, 0.08]	 & \scriptsize [0.24, 0.42, 0.80, 1.0]		 & \scriptsize [0.24, 0.18, 0.56, 0.02] \\

    \scriptsize 3 & \scriptsize [0.73, 0.13, 0.13, 0.01]	 & \scriptsize [0.24, 0.32, 0.91, 1.0]		& \scriptsize [0.24, 0.08, 0.67, 0.01] \\

    \scriptsize 4 & \scriptsize [0.67, 0.24, 0.02, 0.07]	 & \scriptsize [0.19, 0.63, 0.51, 1.0]	& \scriptsize [0.19, 0.44, 0.32, 0.05] \\

    \scriptsize 5 & \scriptsize [0.16, 0.11, 0.04, 0.69]		 & \scriptsize [0.15, 0.71, 0.42, 1.0]			& \scriptsize [0.15, 0.56, 0.27, 0.02] \\

    \scriptsize 6 & \scriptsize [0.26, 0.16, 0.03, 0.55]		 & \scriptsize [0.15, 0.72, 0.40, 1.0]			& \scriptsize [0.15, 0.57, 0.25, 0.03] \\

    \scriptsize 7 & \scriptsize [0.24, 0.46 0.26, 0.04]				 & \scriptsize [0.17, 0.64, 0.53, 1.0]					& \scriptsize [0.17, 0.47, 0.36, 0.00] \\

    \scriptsize 8 & \scriptsize [0.22, 0.28, 0.13, 0.37]				 & \scriptsize [0.15, 0.73, 0.40, 1.0]						& \scriptsize [0.15, 0.58, 0.25, 0.02] \\

    \scriptsize 9 & \scriptsize [0.07, 0.65, 0.04, 0.25]		 & \scriptsize 	[0.00, 1.00, 0.00, 1.0]		& \scriptsize [0.00, 1.00, 0.00, 0.00] \\

    \scriptsize 10 & \scriptsize [0.18, 0.08, 0.01, 0.73]			 & \scriptsize 	[0.18, 0.63, 0.51, 1.0]			& \scriptsize [0.18, 0.45, 0.33, 0.04] \\

    \end{tabular}
        \caption{Ten weak-stochastic nondominant polices computed by our algorithm for the Garden case study.
        %

    }
    \label{tbl:nondom_policies}
    \end{table}

    For each policy, the last column shows probability vector indicating the probability distribution over individual outcomes $p_1,\ldots, p_4$ (in this order) given the computed policy.
    %
    The third column shows the multi-objective value vector of each computed policy. It is noted that
    none of those value vectors dominates any other value vector.
    %
    %

    Rows $1$ and $3$ of this table show that even if the weight assigned to the most preferred outcome, $p_1$, is significantly higher than the weights assigned to the other preferences, the probability that $p_1$ to be satisfied is still less than $0.25$.
    %
    This is justified by the fact that the robot's battery capacity supports the robot for only $12$ time steps and thus to achieve $p_1$, the robot must not be stopped by the bird nor there should be raining when it reaches a cell to do pollination. The probability to satisfy these conditions given the environment dynamics is less than $0.25$.
    %
    The probability of $p_4$ to be satisfied in any entry of this table is less than $0.05$. This is because $p_4$ has the lowest priority, and any policy would prefer to satisfy other preferences who are assigned higher priorities.
    %
    Although the objectives $\{p_1, p_2\}$ and $\{p_1, p_3\}$ in the first and the third rows are treated almost equally by the weight vector in terms of importance, the probability that the later to be satisfied is significantly bigger than the probability of the former to be satisfied. This is because the objective $\{p_1 \}$ contains the preference with the highest priority and that those two rows assign a very high weight to this objective, forcing the policy to try to satisfy $p_1$. Further, by attempting to perform $p_1$, the robot has the chance to accomplish $p_3$ within the same attempt, albeit if it fails to accomplish $p_1$.

    %
    More precisely, if in attempting to perform the task $p_1$---first tulips and then at least one out of daisies and orchids---the robot succeeds to pollinate the tulips but fails to pollinate the daisies and orchids, then it has already accomplished $p_3$, even though it has failed in accomplishing what it was aiming for---$p_1$.
    %

    \subsection{Stochasticity in the Robot's Actions}
    %
	%
	The MDP for this variant has the same number of states, $10,460$, but it has more transitions, $779,396$, which is due to  the stochasticity in   robot's dynamics.
	%
	The MDP construction time for this case was $279.85$ seconds and it took $2,129.02$ seconds to make the product MDP. We again computed $100$ weak-stochastic nondominated policies.
	%
	%
	%

Due to the stochasticity in the robot's dynamic, we expect the policy computed for a specific weight vector
	to be less ``attractive'' than a policy computed for the same weight vector of the previous variant.
	%
	We compare those two polices for the weight vector $[0.25, 0.25, 0.25, 0.25]$.
	%
	The probabilities of the preferences to be satisfied for the variant without stochasticity were $[p_1: 0.24, p_2: 0.05, p_3:0.70, p_4: 0.01]$, while those probabilities for the variant with stochasticity were $[p_1: 0.01, p_2: 0.82, p_3:0.12, p_4: 0.05]$.
	%

	%

	While the former policy yields a higher probability of achieving the most preferred temporal goal---$p_1$, the latter policy puts most of its efforts to satisfy $p_2$
	%

	\section{Conclusions and Future Work}
    %
    In this paper, we proposed a finite automaton for specifying user preferences over temporal goals,
    formulated and solved a preference-based temporal planning in stochastic systems.
    %
    The characteristic that distinguishes our work from prior work on temporal logic planning is that our formulation consider the case where the user preferences may have incomparable outcomes, and this, introduces a problem in defining how to compare policies given their distributions over outcomes as well as a problem in designing planning algorithm to solve a preferred policy.
    %

    %
    We use the notion of weak-stochastic ordering to rank different policies.
    %
    Future work may consider other stochastic ordering that are used for ranking probability measures given a partial order over outcomes.
    %

    %

    %

    %

    %
    Another direction will be to extend this work to the planning with preference over temporal goals that are satisfied in infinite time, for instance, recurrent properties and other more general properties in temporal logic. For practical robotic applications, it would be interesting to design an interface that translates  human language preference specifications or human supervisors' feedback to a computational model, such as a preference automaton or its variant, to facilitate human-on-the-loop planning.

    %

	\bibliographystyle{plain}