Implementation Details


Summary of User Procedures

What follows is a general overview of user installation and usage instructions. More complete instructions are provided in Appendix A.

Installation:

The Newton Connection Kit (NCK) is used to install Concur like any other NewtonScript package file. There are no special considerations other than having about 105K of memory available for the application and a medium sized case base.

Preference settings:

The user should set certain preferences before using Concur. For example, there may be certain days of the week and certain times of the day the user is simply unavailable for meetings. Launching Concur and tapping the Preferences button displays a view with check boxes and sliders to express those choices. See Figure 7. Other options include setting the relative importance of the case base attributes and the level at which the case-based reasoner will take automatic actions. A low tolerance setting requires the CBR have a very good match before automatic actions are taken.

Scheduling a meeting:

Both users launch Concur. One or both may select a duration of the proposed meeting and approximately when they want the meeting to occur. They aim their Newtons at each other from an unobstructed distance not exceeding 10 feet, although, 3 feet seems best. They each then tap the Connect button within a few seconds of each other. Concur then begins an automatic sequence to make an infrared communications connection, calculate the times both are available for meetings and select a possible meeting time.

When Concur finds an available meeting time, the user is presented with a window asking if the proposed time is satisfactory. If so, the user taps the Concur button and the time is beamed to the other user for their concurrence. If both agree, the meeting time may be automatically added to the calendar soup and for viewing with the built-in Dates application.

If the proposed time is not satisfactory, the user may tap the Earlier or Later button to find another time. The time may be advanced, or retarded, by days instead of hours, by selecting the appropriate radio button before tapping the Earlier or Later buttons. If the situation seems hopeless, the user may tap the Quit button.


Figure 7. Preferences View

Program Description

Here is a brief description of the overall logic used by Concur to arrive at mutually agreeable meeting times.

  1. Both users launch Concur. The main screen, illustrated in Figure 2, is presented. Status and user guidance information is provided in the status box near the bottom of the screen. If there are problems, the nature of the problem is also displayed in the status box. If the user taps the "Options" button, the view shown in Figure 7 is presented. The preferences view allows the user to define days and times that are simply not available for meetings and alter the nearest neighbor weighting factors by moving the sliders. Tapping OK will save the changes while tapping cancel will ignore all changes.

    Message and Processing Flow Overview


    Figure 8. Message and Processing Flow Overview

  2. One or both users enter the proposed duration of the meeting, an approximate "try for" interval before the meeting and the amount of pre-meeting preparation time required, if any. The users that make selections for duration and "try for" are termed proposers. (Selecting extra preparation time does not make that user a proposer but the requested time will be honored.)

  3. Both users aim their MessagePad at the other MessagePad and tap their connect buttons.

  4. The Newtons establish an IR connection by alternating between passive and active modes until a connection takes place or a timeout occurs.

    At this point Concur uses a single message handler to control the remainder of its processing logic. This message handler is entered whenever a message is received and depending on the message type, appropriate logic modules are invoked. The handler is also symmetric so that the same code can reside all machines.


    Figure 9. MsgHandler Logic

    The non-primary Newton prepares an M2 message that includes its own Avail array. The meeting duration and approximate meeting time are obtained from the M1 message. This being the first M2 message, the suggested meeting time is set to nil. Later the suggested meeting time will have a value.

    Upon receipt of an M2 message, the Newton compares a non-nil suggested meeting time with its own last suggested meeting time. If the times agree, we have concurrence and the user is asked for permission to add this meeting to the calendar soup. See Figure 10. If the suggested meeting time comparison fails, the Newton then compares the two Avail arrays to determine a suggested meeting time. The case-based reasoner is then consulted for an exemplar to suggest if that will be an acceptable time or if the time should be moved.

    The word "target" below refers to a suggested meeting time.


    Figure 10. Add To Calendar View

  5. Wait for a message. If a message is not received within 10 seconds, goto 15.

     a. If message is "_connect", goto 6.

     b. If message is "M1", goto 7.

     c. If message is "M2", goto 8.

     d. If message is "M3", goto 10.

     e. If message is "M4", goto 13.

     f. If message is "_disconnect", goto 14.

  6. Send M1 message containing proposed meeting information to the other Newton. Initialize last target to nil. goto 5.

  7. Calculate the later of the "try for" times, the longer duration and a matrix of times that this user can meet. Send this information via message "M2". Initialize last target to nil. goto 5.

  8. Retain the "try for" time, the duration, set direction to search forward. goto 11.

  9. If the new target is:

     a. not equal to the last target, go to 11.

     b. equal to the last target, send an M4 message and go to 13.

  10. Add old time to the Cannot array and if a direction change, recalculate the Avail array. goto 11.

  11. . Calculate a new meeting time by searching the Avail matrices of both Newtons. Prepare a probe for the CBR and search it for the nearest neighbor. Returns an action and distance.

     a. If distance is higher than tolerance, goto 12.

     b. If action is accept, goto 12.

     c. If action is earlier or later, do not change direction, goto 10.

  12. Present time to user.

     a. If earlier or later buttons pressed, set search direction, goto 10.

     b. If abort button pressed, send M5, goto 15.

     c. If concur button pressed, send M3, goto 5.

  13. Advise the user that concurrence has been reached and if permitted, add the meeting to the Calendar soup, go to 15.

  14. Display the shutdown message text, go to 15.

  15. Reset IR drivers and terminate Concur.


Figure 11. FindTime Logic

Figure 12. DoButton Logic

Presenting Times to the User

As discussed earlier, if the degree of match exceeds the level indicated by the confidence slider in the options view, the action will be taken automatically. If less than that confidence threshold, the suggested meeting time is to be presented to the user for action.

The user may select from four basic choices; "Concur", "Earlier", "Later" and "Quit". "Concur" causes a message, M3, with this suggested meeting time to be sent back to the other Newton. "Later" causes the suggested time to be added to the Cannot array and the calculations to begin again with the target time advanced by either an hour or a day. Earlier" does the same thing except that the target is moved in the other direction. Because meeting times are suggested on the basis of "earliest first", if that time is not available the target keeps searching in that direction until a time is found. Finally, "Quit" simply ends the session and severs the connection after sending a message to the other Newton.

Adding Cases to the Case Base

New cases will be added to the case base only if there is not an exact match between the probe and the exemplar. This is in contrast to the strategy where a case is added only if the previous nearest neighbor was not within the acceptance tolerance. The objective here was to acquire as much insight, or learning, as quickly as possible. New case frames are the same as the probe frame with the addition of slots for the actual outcome and the time-last-an-exemplar. The frame is indexed and added to the case base. If the probe and the exemplar are identical but their actions differ, the exemplar's action is changed to reflect this new learning.

As the size of the case base grows, the user may want to reduce it to conserve memory albeit at some expense to recommendation quality. The size of the case base is reduced by removing those cases with the oldest time-last-an-exemplar. The view shown in Figure 13 provides that capability. When the "reduce size" button is tapped, the case base, already indexed on time-last-an-exemplar, will have an appropriate number of cases deleted. There is some risk, however, that the quality of some recommendations will be lower because what might have been an infrequent case but the best exemplar, was removed from the case base.


Figure 13. Case Maintenance View

Coding Strategy

Concur is structured like other Newton applications with a traditional view hierarchy. The main application view is the root view and all of the other views are anchored, or linked, to this view. Figure 14 illustrates the view hierarchy.



Figure 14 - View Hierarchy

It was observed early in the design process that there were going to be a large number of functions and global variables defined at the application view level unless something were done to correct the situation. Prototype and instance inheritance is supported by NewtonScript but classes are not. A class may be simulated with careful coding and a few concessions.

The decision was to strive for a high degree of modularity by defining frames at the application view level that consolidated the data and functions common to a specific goal such as maintaining preferences data, performing time calculations, manipulating the case-based reasoner. These frames do not provide data hiding for private data although a high degree of encapsulation is achieved. These modules, in some cases, have knowledge of other parts of the application and may refer to global data or invoke application level functions. However, no outside code refers to the frames' "private" data. This frame based modularity also simplified the coding and editing processes by bringing associated data and functions into single text files. It also allows the easy use of other text editors.

One frame, for IR communications, was sufficiently abstract with good prospects for reusability that a full class simulation was attempted. It is a self-contained class definition with a simple API, flexible transmission options and robust transmission retry support. It also supports a single connection entry point allowing interface designers the opportunity to use a single connect button.

"Global" Data

All global data is defined as slots within a single frame slot. This simplifies navigating the NTK during development.

   g: nil,
   GlobalData:
      {
         prefs:
            {
                     [see below]
            },

         duration:      nil,       // duration of meeting (minutes)
         proposer:      nil,       // set to true if select try after or duration
         who:           nil,       // the other party we will be meeting with (string)
         when:          nil,       // when we will be meeting (time in minutes)
         xtra:          0,         // extra preparation time before meeting (minutes)
         involvement:   2,         // degree of involvement in meeting (0..5)
         myTryFor:      nil,       // my start looking for a time here
         myNAT:         nil,       // my not-after-time (epoch time in minutes)
         tryFor:        nil,       // start looking for a mutually agreeable time here
         NBT:           nil,       // THE not-before-time (epoch time in minutes)
         NAT:           nil,       // THE not-after-time (epoch time in minutes)

         prefsStore:    nil,
         prefsSoup:     nil,
         prefsEntry:    nil,
      }
All of the persistent preferences data is organized as a single frame within the global data frame. This simplifies access, loading and saving. The frame definition and initial values follow.
   prefs:                         // preferences (may be overloaded from the prefs soup)
      {
         name:             "",
         mailSystem:       nil,   // unused
         newtonuniqueid:   nil,   // unused

         dowNotAvail:      [nil, nil, nil, nil, nil, nil, nil],   // sun,mon,tue,wed..sat
         timesNotAvail:    [[0,32], [48,52], [68,96]],            // 12-8, 12-1, 5-12
                                                                  // one unit = 15 min
         CBRon:            nil,
         tolerance:        10,

         riStartTime:      5,     // relative importance of general start time
         riDuration:       5,     // relative importance of general duration
         riDayOfWeek:      5,     // relative importance of day of week
         riWithWhom:       5,     // relative importance of meeting with whom
         riIntervalAfter:  5,     // relative importance of time since earlier meeting
         riIntervalBefore: 5,     // relative importance of time before next meeting
         riInvolvement:    5,     // relative importance of degree of involvement
         riSchedSameDay:   5,     // relative importance of
         riSchedPrevDay:   5,     // relative importance of start time
         riSchedNextDay:   5,     // relative importance of start time
      },

IR Class Definition

The need for robust message transmission and a single button connect features suggested the IR communications module become a fully encapsulated and portable class definition, even if "simulated." The resulting API for the IR class' external methods is shown in Figure 15.

   :New(view, slot);
            view    = host (parent) of instance,
            slot    = slot of instance (self)
   :Connect(bias, connect, fail, display, timeout);
            bias    = true/nil (true if want to begin in active mode)
            connect = symbol to call if good connection
            fail    = symbol to call if time out
            display = symbol to call if to display message.  may be nil.
   :Connected(); returns true if connected, nil otherwise
   :Primary(); returns true if in the active mode when connected
   :ReadyToRecvFrame(msgHandler);
   :SendFrame(frame);
   :Disconnect(text);
Figure 15 - IR Class API

When instantiated, the IR class will be a slot in, perhaps, the application's root view using a NewtonScript statement such as

IR := infraredClass:New(app, 'IR);

The New() method is passed two arguments; one being the view the slot resides in and the other being the symbol for the slot. This information is needed later should the instance disappear for some reason, e.g. the application being closed, and there are outstanding delayed actions. When fired, delayed actions test for the existence of the view and the slot before continuing and if the application is closed, neither the view or the slot will exist.

The Connect() method is passed several arguments. The first is a boolean value, and if true, it tells the IR communications module to start the connection process in the connect or active mode. If nil, the mode is chosen by lot. The next three arguments are symbols for callback routines. One is for when a successful connection is effected (the primary Newton only), another is for when no connection is effected within the timeout interval and the last is to receive information to the user (may be nil). The final argument specifies how long to keep trying and 15 (seconds) seems to be a good value.

The Newton OS supports two flexible methods for sending data between communication endpoints. One method, Output(), is typical of other computer systems where virtually any type and amount of data may be sent and the programmer assumes the responsibility for ensuring both ends understand the format of the data. The other method, OutputFrame(), is unique in that the programmer passes a frame to be sent and that frame is received intact on the other end. The Newton OS automatically flattens the hierarchical frame structure for transmission and automatically reconstructs it upon receipt. This affords a high degree of flexibility when defining data structures and greatly simplifies the mechanics of moving data from one machine to another, especially when the data includes variable sized arrays. All of the messages Concur sends between the Newtons are sent as frames using OutputFrame().

Certain slot names in the transmitted messages have reserved names. They are: _msgNumber, _ack, _connected and _disconnect. _msgNumber is a slot present in all of the messages and its value is the message number assigned to this message. The _ack slot is used to acknowledge a message transmission and its value is the message number being acknowledged. When a connection is effected, a dummy message with a _connected slot is sent to the message handler of the Newton that connected in the active mode. This is its clue that it may begin communications. The second Newton is setup to receive messages. (If the first Newton is not the one to begin the communications for some reason, then a frame should be sent to the other Newton with a _connected slot in it. This will allow the IR class to be fully symmetrical.) If the _disconnect slot is present, it is the signal to disconnect and if it's value is text, that text is displayed to the user via one of the call back addresses provided when the connection was requested.

Even though the connection mode will be known by the primary Newton when its message handler receives a _connected frame slot, two methods are provided for later interrogation of the IR communications module. Connected() will return true or nil depending on the current connection status and Primary() will return true if this Newton was in the active mode at the time of connection and nil otherwise.

IR communications are bi-directional but half duplex. That is, if a Newton is sending, it cannot receive. The normal process is:

IR:SendFrame(frameToSend);

IR:ReadyToRecvFrame('msgHandler);

SendFrame() disables the IR from receiving and sends the frame. Because multiple frames may be sent and the next message handler routine may vary, ReadyToRecvFrame() is used when ready to receive transmissions. Provide it the symbol of the message handler to call when a transmission is received.

Finally, when ready to disconnect, call Disconnect(). If a text parameter is provided, that text is sent to the other Newton and will be displayed if the other Newton provided a display symbol to its IR communications module.

Concur's IR Message Frame Definitions

The following message types have been defined to meet Concur's communication needs. Unless otherwise defined, all times are in minutes where zero is January 1, 1924 and Concur uses the standard Newton OS date and time conversion routines.

The M1 message is sent from the Newton that was in the connect or active mode at the time of connection. This shall be referred to as the first Newton. The frame contains the name of the user, the suggested meeting duration, and the period of time to wait before scheduling the meeting and the connect time. If there is a wide difference in the connect times of the two Newtons, nominally one hour, a message will be displayed to the users advising they synchronize their times.

   { msgType:       kM1,           // a constant defining this message type
     connectTime:   Time(),        // the time the connection was made to
                                   // allow the users to synchronize their
                                   // Newton's time if significantly different
     who:           g.prefs.name,  // Newton's user
     tryFor:        g.myTryFor,    // the interval before the meeting is to
                                   // occur should the user have selected
                                   // it, otherwise 0
     nat:           g.myNAT,       // the "not after time" nominally 1
                                   // month ater the "try for" time, if
                                   // selected, otherwise kInfinity
     duration:      g.duration,    // the duration selected by the user,
                                   // otherwise 0
   };

The M2 message is sent from the second Newton back to the first and contains the resolved "try for" times and durations. The initial search window is defined by the nat and nbt times. avail is the user's Avail array that the other Newton may use to find mutually agreeable meeting times. Likewise, the other Newton's connect time is provided so that the time message may be displayed to both users. The Avail array is sent so the other Newton can calculate a mutually available time.

   { msgType:       kM2,           // a constant defining this message type
     connectTime:   Time(),        // the time the connection was made to
                                   // allow the users to synchronize their
                                   // Newton's time if significantly
                                   // different
     who:           g.prefs.name,  // Newton's user
     tryFor:        g.tryFor,      // the interval before the meeting is to
                                   // occur should the user have selected
                                   // it, otherwise 0
     nbt:           g.NBT,         // not before time
     nat:           g.NAT,         // not after time
     duration:      g.duration,    // the duration selected by the user,
                                   // otherwise 0
     avail:         TC.avail,      // the first Avail array
   };

The M3 messages suggest possible meeting times and are sent back and forth until the users reach concurrence. when is the suggested time. Another Avail array is sent to facilitate time calculations and will be different from previous Avail arrays if there were rejections to presented times.

   { msgType:       kM3,           // a constant defining this message type
     nbt:           base.g.NBT,    // not before time
     nat:           base.g.NAT,    // not after time
     when:          base.g.when,   // a meeting time acceptable to the
                                   // other party
     avail:         avail,         // a subsequent Avail array
   };

The M4 message is sent when the user agrees with the last meeting time proposed by the other user.

   { msgType:       kM4,           // a constant defining this message type

   };

Time Calculations and the Cannot, Avail and AA Arrays

The first step in finding mutually available meeting times involves calculating an array of times one cannot meet called the Cannot array. It is an array of frames each having slots for the beginning and ending times for each window of time one is not available for meetings. The times one is available is kept in a variable sized array of two element tuples containing the beginning and ending time of availability. This is called the Avail array. When it is being constructed, no times are entered that are shorter than the duration plus the request prep time. When two or more Avail arrays are assembled for the purpose of finding a mutually agreeable time, they are organized in an AA array to present all of these times in a uniform manner to the other calculation routines. The AA array is simply an array of Avail arrays where the zeroth element is the local Avail array.

The time calculations are carried out by the following 8 subroutines.

BuildMyCannotArray(nbt, nat) builds the Cannot array within the specified bounds. It gets its information from two sources. The first source is the CalendarSoup and the RepeatMeetingsSoup using the undocumented global routine GetAllMeetings. The other source is the days and times indicated by the user in Concur's preferences view.

AddToCannot(start, span) will identify the specified time interval as unavailable by adding another tuple to the Cannot array.

BuildMyAvailArray(nbt, nat) first checks to see if the Cannot array has been changed and if so, it sorts the Cannot array and constructs a fresh Avail array. No blocks of time are added that are smaller than the meeting duration plus the requested prep time. The Avail array is put into the zeroth slot of the AA array.

AcceptOtherAA(otherAvailArray) adds the other Newton's Avail array to the AA array to provide the remaining calculation routines with a uniform view of available times.

FindMutualTime(nbt, nat, dir) searches the AA array for a time when all can meet between the nbt and the nat searching in the direction of dir.

AdvanceByIncrement(tim, button) will advance the search time by the amount indicated by tim (originally indicated by the present time radio buttons). It adds the previously suggested time to the Cannot array sop that the same time will not be presented again. It is smart enough to know that if duration is 2 hours and the advance increment is 15 minutes, only a 15 minute period is blocked at the time of the meeting. The algorithm handles all the other combinations as well. It is able to distinguish between a button being pushed and the CBR's recommended actions.

FindAnotherTime(nbt, nat, button, oldTime, dir) is called by ProcessButton, MessageHandler and itself, recursively, in the quest to find another time. New times are tested against the CBR for matches within the tolerance value for automatic action or are are presented to the user. When user actions and automatic actions of the type earlier or later are requested, it calls itself to find another time.

ProcessButton(button) is the receiver when any of the four present time buttons are tapped. If earlier or later are tapped, FindAnotherTime is called with the search direction and time adjusted accordingly.

Continue


Original paper: Copyright 1995 by Larry Bugbee
This HTML rendering: Copyright 1997 by Larry Bugbee
All rights reserved.