Technical University of Munich, Department of Computer Science
MQM Paper: [Gupta/Struss 95b]
 

Vineet Gupta, Peter Struss

Representing a Paper Path in a Photo Copier.
(extended abstract of [Gupta/Saraswat/Struss 95])

In: Leonie Dreschler-Fischer, Simone Pribbenow (Eds.): KI-95 Activities: Workshop, Posters, Demos. Gesellschaft für Informatik GI, pp. 119-120, 1995.

Abstract

Our work addresses a problem of spatial representation arising in a real domain: modeling paper transportation in a photo copier. Actually, it is more a case study on how to avoid sophisticated spatial reasoning, or, at least, to simplify it significantly.

In principle, a sheet transported in a copier corresponds to a 2-dimensional surface being deformed and moving around in a 3-dimensional space in a continuous way (unless it tears). A model based on this spatial representation would be very complex. It turns out that a simpler representation suffices to solve many interesting problems in the domain. It is obtained by considering a cross-section of the actual 2-dimensional paper path, as for instance depicted in Fig. 1, which is a set of contiguous curve sections. We ignore the curvature of these sections and consider distances only along the trajectory. This gives us locally a representation by an interval of the real number line-except at branch points, which we have to take into account as they occur in our domain as illustrated by our introductory example. Indexing the maximal linear sections of the paperpath by integers N, and denoting the length of the section by lengthi, we represent a section by a pair section (i) = (i,(0, lengthi))  N  I (R0+),where I (R0+) is the set of intervals on the positive reals (including 0). The point locations on the sections are then described by SECTIONPOINTS = {(i, li) | 0  <  li lengthi N  R. The structure of the path is captured by a set of branching points that sit between sections and specify which sections are possibly connected (perhaps depending on the state of a gate). Let BRANCHINGPOINTS be the set of these points.

Fig. 1. A simple photocopier

Thus the paperpath is represented by

PATH = SECTIONPOINTS  BRANCHINGPOINTS

with an appropriate topology on PATH that treats the branching points as least upper bounds or greatest lower bound resp. of the section intervals. Thus each branching point bk determines a set of (potentially) connected sections, i.e. all sections that intersect with arbitrarily small open neighborhoods of bk . Let connections (bk) = {(i, j) | i  j N  N denote the set of (theoretically) possible section transitions of bk.

To describe the motion of points along PATH, we need a generalized derivative of pathpoints that takes transitions at branching points into account: for p  PATH,

d/dt p = (trans, v (N  N R,

where v is the real-valued velocity, and trans = (i, j) specifies a transition from one section to another one. Of course, this is interesting only at branching points, as for any point on section i, trans = (i, i). trans has to be continuous at branching points in the sense that it can change from (i, i) to (j, j) only by going through (i, j).

With this representation of the paperpath the problem of modeling the motion of a sheet is basically turned into a 1-dimensional locally linear problem which can be handled by real-valued variables, except for branching points, where a decision has to be made about the continuation of motion.

The essential characterization of the motion of a sheet is obtained from the motions of its leading and trailing edge. Gates, which control the branching, are located at branching points and characterized by a (possibly dynamically changing) set of physically possible connections, a subset of the connections determining the topology at the branch. If the leading edge reaches the gate, trans in its derivative is restricted to the (currently) possible connections of the gate. Also the occurrence of buckling can be determined, namely if the length of the sheet segment, i.e. the integral of the difference between the speeds at its left-hand and right-hand bounds, becomes greater than the length of the paper path interval covered by this segment.

Libraries of primitive, local model fragments that can be composed to form a model of a particular scenario are described in detail in [1], [2].

References

1. [Gupta/Struss 95] Gupta, V., Struss, P.: Modeling a Copier Paper Path: A Case Study in Modeling Transportation Processes. In: QR-95, Working Papers of the Ninth International Workshop on Qualitative Reasoning, Amsterdam, 1995. (Also: Tech. Report TR-95-019, International Computer Science Institute, Berkeley, 1995)

2 [Gupta/Saraswat/Struss 95] Gupta, V., Saraswat, V., Struss, P.: A Model of a Photo Copier Paper Path. In: Second Engineering Problems for Qualitative Reasoning Workshop, IJCAI-95, Montreal, Canada, 1995.


If you have comments or suggestions, email me at mauss@in.tum.de
created: Arsineh Keshishian, Aug 25, 1997, last updated: Jakob Mauss, December 4, 1998